leetcode/53.Maximum Subarray.cpp at master · iwccsbfb/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
// divide and conquer
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;
        return maxSubArray(nums, 0, nums.size()-1);
    }
    int maxSubArray(vector<int> &nums, int s, int e) {
        if(s > e) return INT_MIN;
        if(s == e) return nums[s];
        int mid = (s+e)/2;
        int left_res = maxSubArray(nums, s, mid-1);
        int right_res = maxSubArray(nums, mid+1, e);
        // ÐèÒª³õÊ¼»¯Îª0£¬¶ø²»ÊÇINT_MIN!!
        int left_max = 0, right_max = 0;
        int sum = 0;
        for(int i=mid-1; i>=s; i--) {
            sum += nums[i];
            left_max = max(left_max, sum);
        }
        sum = 0;
        for(int i=mid+1; i<=e; i++) {
            sum += nums[i];
            right_max = max(right_max, sum);
        }
        return max(max(left_res, right_res), nums[mid]+left_max+right_max);
    }

    // O(N) time complexity
    int maxSubArray2(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr(n);
        for(int i=0; i<n; i++) {
            int prev = (i==0? 0 : arr[i-1]);
            if(prev <= 0) arr[i] = nums[i];
            else arr[i] = prev + nums[i];
        }
        int res = arr[0];
        for(auto &i : arr) res = max(res, i);
        return res;
    }
};