# DP求解

• class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size();

// sum[i]保存第i个元素之前的所有元素的和，不包括i。leftindex[i]保存了[0, i]中最大的左子序列的startindex。rightindex为右。
vector<int> sum(1, 0), leftindex(n, 0), rightindex(n, n-k), ans(3, 0);

for (int i: nums)
sum.push_back(sum.back() + i);

for (int i = k, max = sum[k] - sum[0]; i < n; ++i) {
if (sum[i+1] - sum[i-k+1] > max) {  // 因为leftindex保存的是[0,i]之间的最大左子序列start，所以要+1。下边rightindex因为是[i,n-1]所以不用+1
leftindex[i] = i - k + 1;
max = sum[i+1] - sum[i-k+1];
} else {
leftindex[i] = leftindex[i-1];
}
}

for (int i = n-k-1, max = sum[n] - sum[n-k]; i >= 0; --i) {
if (sum[i+k] - sum[i] >= max) {  // 注意这里的等号（因为i是递减的，所以后续迭代有等于max也要更新）
rightindex[i] = i;
max = sum[i+k] - sum[i];
} else {
rightindex[i] = rightindex[i+1];
}
}

for (int i = k, max = 0; i <= n - 2 * k; i++) {  // 注意条件的等号
int j = sum[leftindex[i-1]+k] - sum[leftindex[i-1]] + sum[i+k] - sum[i] + sum[rightindex[i+k]+k] - sum[rightindex[i+k]];
if (j > max) {
max = j;
ans[0] = leftindex[i-1];
ans[1] = i;
ans[2] = rightindex[i+k];
}
}

return ans;
}
};

/*
DP思想，定义了F（i）为中间序列的首元素为i时的最大和。前面的三个for循环也是dp，J(i)为从0到i中的最大和。
*/

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.