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