runtime 110 ms, beats 97.84% of cpp submissions
O(n) solution with explanation

tags: dp

Maximum Subarray

📖 description

給定一陣列 nums ，回傳最長子陣列和。

ex.
    Input: 
        nums = [-2,1,-3,4,-1,2,1,-5,4]

    Output: 6

    Explanation: 
        [4,-1,2,1] has the largest sum = 6.

🧠 solution

若使用暴力法，時間複雜度會到 O(n^3) ，其中枚舉所有子陣列需要 O(n^2) ，加總則需要 *O(n)*。
我們可以使用前綴和來避免加總的時間複雜度，將時間複雜度降到 *O(n^2)*。
再更進一步可以利用分治法，藉由將子陣列切割，達到 O(nlog(n)) ，其中計算跨中間總和需要 O(n) ，且共有 O(log(n)) 次切割。
而最簡單的方法是使用 dp ，維護連續區間的最大值，當區間數值 < 0 時，表示目前區間不會出現在最大子陣列中，所以可以重製狀態後再繼續維護區間最大值。

⏳ time complexity

遍歷一次陣列，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ma = 0;
        int now = 0;
        for(int i=0;i<nums.size();i++){
            now+=nums[i];
            if(now<0){
                now = 0;            // 如果過去的區間數值已經小於 0 
            }
            if(ma<now){
                ma = max(ma,now);   // 紀錄最大值
            }
        }
        // 如果沒找到最大值，回傳在陣列中的最大值
        return ma==0 ? *max_element(nums.begin(),nums.end()) : ma;
    }
};