s******b
发帖数: 185 | 1 Maximum Sum of 3 Non-Overlapping Subarrays。
看了半天，答案也看的不是很懂。
这道居然会是高频题？ | u**u
发帖数: 668 | | w*******o
发帖数: 113 | 3 叔这个题目是动态编程。
其实不是很复杂。
1. 就是你先算一下以k为长度，滑动窗口的和，放到一个数组里。
2. 从左到右计算 以i为起点，到i为止，最大值的窗口的起始index
比如说[1,3,2,0]
所对应[0,1,1] 因为 2 + 0 < 3 + 2
3.从右向左计算以z为为起点，从z向右考虑，最大窗口和的起始index
4.因为窗口不能重复，所以i + k <= j + k <= z
在j的范围内遍历并且更新结果就可以了。
代码如下：
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int sum = 0, len = nums.length - k + 1;
int[] sums = new int[len];
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= k) sum -= nums[i - k];
if (i >= k - 1) sums[i - k + 1] = sum;
}
int[] left = new int[len];
int best = 0;
for (int i = 0; i < len; i++) {
if (sums[i] > sums[best]) best = i;
left[i] = best;
}
int[] right = new int[len];
best = len - 1;
for (int i = len - 1; i >= 0; i--) {
if (sums[i] >= sums[best]) best = i;
right[i] = best;
}
int[] res = {0, k, 2 * k};
for (int j = k; j < len - k; j++) {
int i = left[j - k], z = right[j + k];
if (sums[i] + sums[j] + sums[z] > sums[res[0]] + sums[res[1]] +
sums[res[2]]) {
res[0] = i;
res[1] = j;
res[2] = z;
}
}
return res;
}
} | s******b
发帖数: 185 | 4 赞，太厉害了
【在 w*******o 的大作中提到】
: 叔这个题目是动态编程。
: 其实不是很复杂。
: 1. 就是你先算一下以k为长度，滑动窗口的和，放到一个数组里。
: 2. 从左到右计算 以i为起点，到i为止，最大值的窗口的起始index
: 比如说[1,3,2,0]
: 所对应[0,1,1] 因为 2 + 0 < 3 + 2
: 3.从右向左计算以z为为起点，从z向右考虑，最大窗口和的起始index
: 4.因为窗口不能重复，所以i + k <= j + k <= z
: 在j的范围内遍历并且更新结果就可以了。
: 代码如下：
| y**********u
发帖数: 2839 | 5 加油啊叔，这是老题，不能15mins bug free很被动的
【在 s******b 的大作中提到】
: 赞，太厉害了
| w*******o
发帖数: 113 | 6 哈哈，街霸哥。
我先改简历投简历，然后继续做题上poj
【在 y**********u 的大作中提到】
: 加油啊叔，这是老题，不能15mins bug free很被动的
| y**********u
发帖数: 2839 | 7 好的，祝兄弟早日拿到大包，但是啥时候都别忘刷题，这样才能一直拿大包，才能被
pip时不用舔老板ass，才能活的有点尊严，切记切记
【在 w*******o 的大作中提到】
: 哈哈，街霸哥。
: 我先改简历投简历，然后继续做题上poj
| x*******1
发帖数: 28835 | |
|
