# 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;
}
};
```