# Maximum Subarray III

### Description

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.

> The subarray should contain at least one number

**Example**

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

## Analysis

维护一个int globalMax \[ k+1 ] \[ len+1 ] 的矩阵， globalMax \[ i ] \[ j ] 代表了前 j 个数中取 i 个 subarray 得到的最大和， 注意这里第 j 个数不一定被包括。

一个 int 类型 localMax, 每次写第 globalMax 的 第 i 行 第 j 列时用到的， 记录前 j 个数中取 i 个 subarray 得到的最大和， 但包括第 j 个数。

## Solution

```java
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) {
        // write your code here
        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>