任何人都可以在下面引导我完成这个解决方案吗?p是什么意思?为什么它的范围是J-1到I?谢谢给定一个整数数组和一个数字 k,找到 k 个总和最大的非重叠子数组。
每个子数组中的数字应该是连续的。
返回最大金额。
根据这个博客(http://www.cnblogs.com/lishiblog/p/4183917.html),DP分析是
d[i][j] 表示我们从前 i 个元素中选择 j 个子数组可以获得的最大和。
d[i][j] = max{d[p][j-1]+maxSubArray(p+1,i)}
我们将 P 从 I-1迭代到 J-1,因此我们可以记录我们在当前 P 处获得的最大子数组,当 P 变为 P-1 时,该值可用于计算从 P-1 到 I 的最大子数组。
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(ArrayList<Integer> nums, int k) {
if (nums.size()<k) return 0;
int len = nums.size();
//d[i][j]: select j subarrays from the first i elements, the max sum we can get.
int[][] d = new int[len+1][k+1];
for (int i=0;i<=len;i++) d[i][0] = 0;
for (int j=1;j<=k;j++)
for (int i=j;i<=len;i++){
d[i][j] = Integer.MIN_VALUE;
//Initial value of endMax and max should be taken care very very carefully.
int endMax = 0;
int max = Integer.MIN_VALUE;
for (int p=i-1;p>=j-1;p--){
endMax = Math.max(nums.get(p), endMax+nums.get(p));
max = Math.max(endMax,max);
if (d[i][j]<d[p][j-1]+max)
d[i][j] = d[p][j-1]+max;
}
}
return d[len][k];
}
}
p是什么意思:只是一个迭代器。(中文算法编码器总是喜欢变量的简称...
为什么它的范围j-1到i:
实际上,dp 分析应该是:
d[i][j] = max{d[p][j-1]+maxSubArray(p+1,i)} j-1 <= p <= i-1
为什么p >= j-1?因为正如 dp[i][j] 定义的那样:
d[i][j] 表示我们从前 i 个元素中选择 j 个子数组可以获得的最大和。
你知道,我们不能选择j子数组而不从j-1元素中不重叠。也就是说,当 i>= j 时,dp[i][j] 是有意义的。
如有任何问题,请在此处发表评论。