【題解】LeetCode - 53. Maximum Subarray

題目連結

題目大意

給定一個長度為 $n$ 的數列 $a_0, \dots, a_{n - 1}$，求最大連續和。

• $1 \leq n \leq 10^5$
• $|a_i| \leq 10^4$

題解

最大連續和有兩種經典的作法，DP 和分治。

DP

定義 $dp[i]$ 為考慮 $a_0, \dots, a_i$ 且包含 $a_i$ 的最大連續和。不難發現如果 $dp[i - 1] < 0$，則單獨取 $a_i$ 會更好，因此我們得到 $dp[i] = max(dp[i - 1], 0) + a_i$。因為 $dp[i]$ 都只跟 $dp[i - 1]$ 有關，因此我們只需要用一個變數去紀錄前一項的 $dp$ 值就好了。時間複雜度為 $O(n)$。

class Solution {
public:
    int maxSubArray(vector<int>& a) {
        int ans = INT_MIN;
        int dp = 0;
        for(auto x : a) {
            dp = max(dp, 0) + x;
            ans = max(ans, dp);
        }
        return ans;
    }
};

分治

定義 $solve(l, r)$ 為 $a_l, \dots, a_{r - 1}$ 的最大連續和，最後所求就是 $solve(0, n)$。假設我們現在要求 $[l, r)$ 的最大連續和，令 $m = \lfloor \frac{l + r}{2} \rfloor$，$[l, r)$ 的最大連續如果完全落在 $m$ 的左邊，則在呼叫 $solve(l, m)$ 時就會被找到。相同的，如果完全落在右半邊，則呼叫 $solve(m, r)$ 時會被找到。最後一個情況是最大連續和橫跨 $m$，那麼就會是 $[l, m)$ 的最大後綴和 $+$ $[m, r)$ 的最大前綴和。這兩個東西都能夠在 $O(r - l)$ 求出。綜合上述的做法，我們得到 $T(n) = 2T(\frac{n}{2}) + O(n)$，根據主定理我們得到 $T(n) = O(n \log n)$。

我們其實還能夠做的更好。最大前綴和和最大後綴和在函數回傳的時候可以一併維護，這樣我們就不用額外花費 $O(r - l)$ 的時間去計算。複雜度為 $T(n) = 2T(\frac{n}{2}) + O(1)$，$T(n) = O(n)$。

分治 $O(n \log n)$ 作法

class Solution {
public:
    int maxSubArray(vector<int>& a) {
        return solve(a, 0, a.size());
    }
    
    int solve(const vector<int>& a, int l, int r) {
        if(l + 1 == r) {
            return a[l];
        }
        int m = (l + r) / 2;
        int ans = max(solve(a, l, m), solve(a, m, r));
        int pref = 0, max_pref = INT_MIN;
        for(int i = m - 1; i >= l; i--) {
            pref += a[i];
            max_pref = max(max_pref, pref);
        }
        int suff = 0, max_suff = INT_MIN;
        for(int i = m; i < r; i++) {
            suff += a[i];
            max_suff = max(max_suff, suff);
        }
        ans = max(ans, max_pref + max_suff);
        return ans;
    }
};

分治 $O(n)$ 作法

class Solution {
public:
    int maxSubArray(vector<int>& a) {
        auto [ans, max_pref, max_suff, sum] = solve(a, 0, a.size());
        return ans;
    }

    tuple<int, int, int, int> solve(const vector<int>& a, int l, int r) {
        if(l + 1 == r) {
            return {a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) / 2;
        auto [ans_l, max_pref_l, max_suff_l, sum_l] = solve(a, l, m);
        auto [ans_r, max_pref_r, max_suff_r, sum_r] = solve(a, m, r);
        int ans = max(ans_l, ans_r);
        ans = max(ans, max_suff_l + max_pref_r);
        int max_pref = max(max_pref_l, sum_l + max_pref_r);
        int max_suff = max(max_suff_r, sum_r + max_suff_l);
        int sum = sum_l + sum_r;
        return {ans, max_pref, max_suff, sum};
    }
};

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】LeetCode - 53. Maximum Subarray