题目
核心思路
这道题应该算是困难题目里比较简单的一道了，最关键的就是知道怎么优化来提高效率。首先给出一种暴力法，先穷举出所有的可能，然后去发现可以优化的地方。
暴力法
想要穷举所有可能，对于题目中提到的3个子数组，显然需要至少三层循环，我们设i , j , m分别表示三个子数组的结尾下标(开头也相同)，那就需要三层循环来遍历i , j , m，然后还要从这三个下标分别向前求 k 个数的和，也就是说总共需要四层循环，复杂度十分可怕，代码就不给出了。
优化一
这是一种很常见的方法，就是求前缀和，通过前缀和来求子数组的和可以省去一层循环，即知道结尾下标之后向前遍历求和的过程。
代码
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] ans = new int[3];
int[] sum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
//求前缀和
sum[i + 1] = sum[i] + nums[i];
}
for (int i = nums.length; i >= k; i--) {
//求长度为k的子数组的间隔和
sum[i] = sum[i] - sum[i - k];
}
int maxSum = 0;
//遍历
for (int i = k; i <= nums.length - 2 * k; i++) {
for (int j = i + k; j <= nums.length - k; j++) {
for (int m = j + k; m <= nums.length; m++) {
if (maxSum < sum[i] + sum[j] + sum[m]) {
maxSum = sum[i] + sum[j] + sum[m];
ans[0] = i - k;
ans[1] = j - k;
ans[2] = m - k;
}
}
}
}
return ans;
}
}
思路仍是暴力，但是通过求前缀和的预处理，把最内层的循环省掉，提高一些效率。
优化二
一种直观的想法：如果只找数组中一个最大的数，直接用一个变量遍历一遍即可；那么如果i , j , m的下标范围是确定的，问题就会变得同上边的想法，变得很简单。不过这道题要求的是长度为k的子数组，范围就是可变的了。但是如果固定中间位置的下标 j ，此时他前后两个子数组 i , m的下标就变成固定范围了，固定范围肯定就会有一个最大值(即最优解)，问题有局部最优解，也就须要用到DP了。
所以我们使用一个 left 数组保存第一个子数组的局部最优解，用一个 right 数组保存最后一个子数组的局部最优解，然后遍历每一个可能中间下标 j，就可以求出最终答案，并且可以省去两层循环，效率大大提高。
代码
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] ans = new int[3];
int[] sum = new int[nums.length + 1];// 长度+1，sum[0] = 0方便求前缀和
int[] left = new int[nums.length + 1];// 长度与sum一致方便运算、理解
int[] right = new int[nums.length + 1];// 同上
// 求前缀和
for (int i = 0; i < nums.length; i++) {
sum[i + 1] = sum[i] + nums[i];
}
// 求间隔为k的和，从下标k开始求，以结尾为主
for (int i = nums.length; i >= k; i--) {
sum[i] = sum[i] - sum[i - k];
}
// 求从左边开始，和最大的值最早出现的下标
int maxNum = 0;
int index = 0;
for (int i = k; i <= nums.length - k * 2; i++) {
if (maxNum >= sum[i]) {// >=号保证存储的是最先出现的下标
left[i] = index;
} else {
left[i] = i;
index = i;
maxNum = sum[i];
}
}
// 求从右边开始，和最大的值最早出现的下标
maxNum = 0;
index = 0;
for (int i = nums.length; i >= k * 2; i--) {
if (maxNum > sum[i]) {// >号保证存储的是最先出现的下标
right[i] = index;
} else {
right[i] = i;
maxNum = sum[i];
index = i;
}
}
// 遍历j可能的位置，求出所有可能的最大值
maxNum = 0;
for (int i = k * 2; i <= nums.length - k; i++) {
if (maxNum < sum[i] + sum[left[i - k]] + sum[right[i + k]]) {
maxNum = sum[i] + sum[left[i - k]] + sum[right[i + k]];
ans[0] = left[i - k] - k;// - k由于求间隔和的时候，和是存储在每个间隔最后一个元素的下标
ans[1] = i - k;
ans[2] = right[i + k] - k;
}
}
return ans;
}
}
我这里将和数组、left数组、right数组大小都设为 nums.length + 1，主要是为了方便运算，也方便理解，实际上用到的大小只有 nums.length - k 罢了。如有内容错误的地方还请指出，感谢相遇~
