leetcode/Maximum Subarray II at master · aimjwizards/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
   int maxTwoSubArrays(vector<int> nums) {
        // write your code here

        vector<int> pre_max(nums.size(), 0);
        int min_sum = 0;
        int max_sum = INT_MIN;
        int sum = 0;
        for(int i=0; i<nums.size(); i++) {
            sum += nums[i];
            max_sum = max(max_sum, sum-min_sum);
            min_sum = min(min_sum, sum);
            pre_max[i] = max_sum ;
        }

        vector<int> post_max(nums.size(), 0);
        min_sum = 0;
        max_sum = INT_MIN;
        sum = 0;
        for(int i=nums.size()-1; i>=0; i--) {
            sum += nums[i];
            max_sum = max(max_sum, sum-min_sum);
            min_sum = min(min_sum, sum);
            post_max[i] = max_sum;
        }
        int result = INT_MIN;
        for(int i=0; i< nums.size()-1; i++ ) {
            result = max(result, pre_max[i]+post_max[i+1]);
        }
        return result;
    }