题目描述
给定一个整数数组和一个整数 k，找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
注意事项
子数组最少包含一个数
样例
给出数组 [-1,4,-2,3,-2,3] 以及 k = 2，返回 8
思路
dp[i][j] = max(dp[x][j-1]+maxs[x+1][i])
dp[i][j] 表示前 i 个数中 j 个子数组的最大值，
maxs[i][j] 表示 第i个数到第j个数中最大子数组的和。
代码
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
int[][] maxs = new int[nums.length][nums.length];
int[][] dp = new int[nums.length][k+1];
for(int i=0; i<nums.length; ++i) {
for(int j=i; j<nums.length; ++j) {
maxs[i][j] = maxSum(nums, i, j);
}
}
for(int i=0; i<dp.length; ++i) {
for(int j=0; j<dp[i].length; ++j) {
dp[i][j] = Integer.MIN_VALUE;
}
}
for(int i=0; i<dp.length; ++i) {
dp[i][1] = maxs[0][i];
}
for(int i=1; i<nums.length; ++i) {
for(int j=2; j<=k; ++j) {
for(int x=j-2; x<i; ++x) {
dp[i][j] = Math.max(dp[i][j], dp[x][j-1] + maxs[x+1][i]);
}
}
}
return dp[nums.length-1][k];
}
private int maxSum(int[] nums, int i, int j) {
int sum = 0, maxs = Integer.MIN_VALUE;
for(int x = i; x <= j; ++x) {
sum += nums[x];
if (maxs < sum) {
maxs = sum;
}
if (sum < 0) {
sum = 0;
}
}
return maxs;
}
}
