# 689. Maximum Sum of 3 Non-Overlapping Subarrays

In a given array `nums` of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size `k`, and we want to maximize the sum of all `3*k` entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

``````Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
``````

Note:

• `nums.length` will be between 1 and 20000.
• `nums[i]` will be between 1 and 65535.
• `k` will be between 1 and floor(nums.length / 3).

left[i]表示在区间[0, i]范围内长度为k且和最大的子数组的起始位置

right[i]表示在区间[i, n - 1]范围内长度为k且和最大的子数组的起始位置

``````class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size(), mx = INT_MIN;
vector<int> sums{0}, res, left(n, 0), right(n, n - k);
for (int num : nums) sums.push_back(sums.back() + num);
for (int i = k, total = sums[k] - sums[0]; i < n; ++i) {
if (sums[i + 1] - sums[i + 1 - k] > total) {
left[i] = i + 1 - k;
total = sums[i + 1] - sums[i + 1 - k];
} else {
left[i] = left[i - 1];
}
}
for (int i = n - 1 - k, total = sums[n] - sums[n - k]; i >= 0; --i) {
if (sums[i + k] - sums[i] >= total) {
right[i] = i;
total = sums[i + k] - sums[i];
} else {
right[i] = right[i + 1];
}
}
for (int i = k; i <= n - 2 * k; ++i) {
int l = left[i - 1], r = right[i + k];
int total = (sums[i + k] - sums[i]) + (sums[l + k] - sums[l]) + (sums[r + k] - sums[r]);
if (mx < total) {
mx = total;
res = {l, i, r};
}
}
return res;
}
};
``````

Best Time to Buy and Sell Stock III

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/discuss/108231/C++Java-DP-with-explanation-O(n)

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/discuss/108246/C++-O(n)-time-O(n)-space-concise-solution

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/discuss/108230/Clean-Java-DP-O(n)-Solution.-Easy-extend-to-Sum-of-K-Non-Overlapping-SubArrays

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation