# Maximum Subarray III

# Question:

http://www.lintcode.com/en/problem/maximum-subarray-iii/

Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

# Answer

```
localMax[i][j], means the maximum sum we can get while select j subarrays from first i elements, including element i
localMax[i][j], means the maximum sum we can get while select j subarrays from first i elements, may not including element i
// state transfer
localMax[i][j] = max(localMax[i - 1][j] + nums[i - 1], globalMax[i - 1][j - 1] + nums[i - 1])
globalMax[i][j] = max(globalMax[i - 1][j], localMax[i][j])
```

```
class Solution {
public:
/*
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
int maxSubArray(vector<int> &nums, int k) {
// write your code here
int n = nums.size();
if (n == 0 || k > n)
return 0;
// Use INT_MIN might cause numeric overflow
vector<vector<int>> localMax(n+1, vector<int>(k+1, INT_MIN/2));
vector<vector<int>> globalMax(n+1, vector<int>(k+1, INT_MIN/2));
localMax[0][0] = globalMax[0][0] = 0;
for (int i = 1; i <= n; i++) {
localMax[i][0] = 0;
globalMax[i][0] = 0;
for (int j = 1; j <= k; j++) {
localMax[i][j] = max(localMax[i-1][j] + nums[i-1],
globalMax[i-1][j-1] + nums[i-1]);
globalMax[i][j] = max(globalMax[i-1][j], localMax[i][j]);
}
}
return globalMax[n][k];
}
};
```