Online Judge Solutions

Saturday, December 6, 2014

LintCode: Maximum Subarray II

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.
Note
The subarray should contain at least one number
Example
For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.

 
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two
     *          Subarrays
     */
    int maxTwoSubArrays(vector<int> nums) {
        int n = nums.size();
        vector<int> maxLR(n, nums[0]);
        vector<int> maxRL(n, nums[n-1]);
       
        int prev = nums[0];
        for(int i = 1; i< n; i++)
        {
           int sum = nums[i] + (prev >0? prev : 0);
           prev = sum;
           maxLR[i] = max(sum, maxLR[i-1]);
        }
        prev = nums[n-1];
        for(int i = n-2; i>=0; i--) {
           int sum = nums[i] + (prev >0? prev : 0);
           prev = sum;
           maxRL[i] = max(sum, maxRL[i+1]);
        }
        int maxSum = INT_MIN;
        for(int i = 0; i < n-1; i++)
           maxSum = max(maxSum, maxLR[i]+maxRL[i+1]);
       
        return maxSum;
    }
};

No comments:

Post a Comment