Given an array of integers and a numberk, find knon-overlappingsubarrays which have the largest sum.
The number in each subarray should becontiguous.
Return the largest sum.
Example
Given[-1,4,-2,3,-2,3],k=2, return8
分析：
动归问题。dp[i][j]表示从前i个数( i.e., [0, i-1]) 中取j个subarray得到的最大值，那么要求的结果就是dp[n][k]：从前n个数中取k个subarray得到的最大和。
状态转移：从前i个中取j个，那么我们可以从前p个数（i.e., [0, p-1]）中取j-1个subarray，再加上从P到i-1这个subarray中的最大和（也就是Maximum Subarray问题）。从这句话里我们也可以读出来p的范围应该是j-1~i-1
d[i][j] = max{d[i][j],d[p][j-1]+maxSubArray(p+1,i)}
public int maxSubArray(int[] nums, int k) {
if(nums ==null || nums.length == 0)
return 0;
int len = nums.length;
//以j结尾的数组里有i个子数组
//f[i][j] = Math.max(f[i][j], f[i-1][m]+ sumFromTo(i-1，j]);
int localMax, max;
int[][] f = new int[k+1][len+1];
int min = nums[0], sum = 0;
for(int i = 1; i <= k; i++){
for(int j = i; j <= len; j++){
localMax = 0; max = Integer.MIN_VALUE;
f[i][j] = Integer.MIN_VALUE;
for(int m = j-1; m >= i-1; m--){//i->j之间最大的subarray sum,需要从后往前算，这样求的是后端固定的maxSum
//从后往前，因为我们只需要从j-1到i-1内最大的，前面开始的话包括了i-1之前的值。和back-forward概念一样
//locaMax一定以当年Nums[m]结尾的sum，但是max不一定以当前结尾，而是截止到m为止最大，可有该nums[m]可无
localMax = Math.max(nums[m], localMax + nums[m]);
max = Math.max(localMax, max);
f[i][j] = Math.max(f[i][j], f[i-1][m]+ max);
}
}
}
return f[k][len];
}
分析：
local[i][k]表示前i个元素取k个子数组并且必须包含第i个元素的最大和。
global[i][k]表示前i个元素取k个子数组不一定包含第i个元素的最大和。
local[i][k]的状态函数：
max(global[i-1][k-1], local[i-1][k]) + nums[i-1]
local有两种情况，第一种是第i个元素自己组成一个子数组，则要在前i－1个元素中找k－1个子数组，第二种情况是第i个元素属于前一个元素的子数组，因此要在i－1个元素中找k个子数组（并且必须包含第i－1个元素，这样第i个元素才能合并到最后一个子数组中），取两种情况里面大的那个。
global[i][k]的状态函数：
max(global[i-1][k]，local[i][k])
glocal有两种情况，第一种是不包含第i个元素，所以要在前i－1个元素中找k个子数组，第二种情况为包含第i个元素，在i个元素中找k个子数组且必须包含第i个元素，取两种情况里面大的那个
public int maxSubArray(int[] nums, int k) {
int n = nums.length;
// if(n < 1){
// return 0;
// }
//local[i][k]表示前i个元素取k个子数组并且必须包含第i个元素的最大和。
//global[i][k]表示前i个元素取k个子数组不一定包含第i个元素的最大和。
int[][] local = new int[n + 1][k + 1];
int[][] global = new int[n + 1][k + 1];
for(int j = 1; j <= k; j ++){
for(int i = j; i <= n; i ++){
local[j - 1][j] = Integer.MIN_VALUE;//小于 i 的数组不能够partition,取最小防止被取到。
//1.要不i自成一组，不跟前面，所以用global因为前面i-1是否包含都行
//2.要不i跟前面成一组，则i-1必须包含，因为是连续的，所以用local
local[i][j] = Math.max(global[i-1][j-1], local[i-1][j]) + nums[i - 1];
if(i == j){
global[i][j] = local[i][j];
}else{
//1.不取i，所以前面i-1包不包都可以，用global
//2.取i,必须包含i,所以用local
global[i][j] = Math.max(global[i - 1][j], local[i][j]);
}
}
}
return global[n][k];
}