Maximum Subarray II

Question

Given an array of integers, find two non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.

Notice

The subarray should contain at least one number

Answer

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector<int> &nums) {
        // write your code here
        int len = nums.size();
        vector<int> suml(len);
        int cur_max = nums[0];
        int max = cur_max;
        suml[0] = max;
        for (int i = 1; i < len; i++) {
            if (cur_max <= 0) {
                cur_max = nums[i];
            } else {
                cur_max += nums[i];
            }
            if (max < cur_max)
                max = cur_max;
            suml[i] = max;
        }
        vector<int> sumr(len);
        cur_max = nums[len-1];
        max = cur_max;
        sumr[len-1] = max;
        for (int i = len - 2; i >= 0; i--) {
             if (cur_max <= 0) {
                 cur_max = nums[i];
             } else {
                 cur_max += nums[i];
             }
             if (max < cur_max)
                 max = cur_max;
             sumr[i] = max;
        }
        int result = suml[0] + sumr[1];
        for (int i = 1; i < len - 1; i++) {
             int temp = suml[i] + sumr[i+1];
             if (result < temp)
                 result = temp;
        }
        return result;
    }
};

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️