注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号
x
想写一个Dp 的算法, 试了很多遍,都不能保证全过。求指点。想法就是用4个数组,第一个都是0,第二个是1个subarray 的 sum, 但是只记录到此为止的最大值,如果到此为止的sum是10,但是前面有subarray的sum是20,那么就记录20, 第三个数组记录2 个subarray 的 sum, 很显然 2 个 subarray 相加,这两个Subarray不能overlap. 最后一个dp array 就是三个subarray 的 sum. 同时有一个id的数组记录最大值开始的index.
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
// W is an array of sums of windows
int[] W = new int[nums.length - k+1]; //if 6 numbers, k=2, W has 5 numbers
int currSum = 0;
for (int i = 0; i < nums.length; i++) {
currSum += nums[i];
if (i >= k) {
currSum -= nums[i - k];
}
if (i >= k - 1) {
W[i - k + 1] = currSum;
}
}
int[][] dp = new int[4][nums.length-k+2];
int sum = 0;
int[][] id = new int[4][nums.length-k+2];
int max = 0, inId = 0;
for(int i = 1; i < 4; i++) {
for(int j = 1; j <= nums.length-k+1; j++) { //start from index 1 for k=2
if(j<=k)
{
dp[i][j] = W[0];
id[i][j] = 0;
continue;
}
int tmpmax = W[j-1] + dp[i-1][j-k];
//w[j-1] is the sum to current j, dp[i-1][j-k] is the best up to j
if(j - k >= 0) {
dp[i][j] = dp[i][j-1];
id[i][j] = id[i][j-1];
}
if(j > 0 && tmpmax > dp[i][j-1]) {
dp[i][j] = tmpmax;
id[i][j] = j-1;
}
}
}
int[] res = new int[3];
res[2] = id[3][nums.length-k+1];
res[1] = id[2][res[2] - 1];
res[0] = id[1][res[1] - 1];
return res;
}
}
|