# Maximum Subarray III

### Description

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

The number in each subarray should be contiguous.

Return the largest sum.

The subarray should contain at least one number

Example

Given`[-1,4,-2,3,-2,3]`,`k=2`, return`8`

## Solution

``````public class Solution {
/**
* @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
*/
public int maxSubArray(int[] nums, int k) {
if(nums == null || nums.length == 0) return 0;

int n = nums.length;

int[][] localMax = new int[n + 1][k + 1];
int[][] globalMax = new int[n + 1][k + 1];

for(int i = 1; i <= n; i++){
for(int j = 1; j <= k && j <= i; j++){
localMax[j - 1][j] = Integer.MIN_VALUE;

localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1])
+ nums[i - 1];
if(i == j) globalMax[i][j] = localMax[i][j];
else globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]);
}
}

return globalMax[n][k];
}
}
``````

## Reference

https://mnmunknown.gitbooks.io/algorithm-notes/626,\_dong\_tai\_gui\_hua\_ff0c\_subarray\_lei.html