##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/689.html

# 689. Maximum Sum of 3 Non-Overlapping Subarrays

Hard

## Description

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).

## Solution

Use dynamic programming. First calculate the prefix sum of each element and store the sums in array prefixSums, where prefixSums[i] is the sum of all elements from nums[i - k + 1] to nums[i] for i >= k - 1. Then create two 2D arrays dp and path of nums.length rows and 3 columns, where dp[i][j] represents the maximum sum of j + 1 subarrays that end at index i, and path[i][j] represents the corresponding index. Initialize dp[k - 1][0] = prefixSums[k - 1] and path[k - 1][0] = k - 1.

Loop over i from k to nums.length - 1 and j from 0 to 2. For each (i, j), initialize dp[i][j] = dp[i - 1][j] and path[i][j] = path[i - 1][j]. The previous sum is prefixSums[i] + dp[i - k][j - 1], where dp[i - k][j - 1] is 0 if j == 0. If the previous sum is greater than dp[i][j], then update dp[i][j] with the previous sum and update path[i][j] = i.

After the elements in dp and path are filled, find the start indices of each subarray using path and return the array that contains the start indices.

• class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
return maxSumOfNSubarrays(nums, k, 3);
}

public int[] maxSumOfNSubarrays(int[] nums, int k, int n) {
if (nums == null || k < 1 || n * k > nums.length)
return new int[0];
int length = nums.length;
int[] prefixSums = new int[length];
for (int i = 0; i < k; i++)
prefixSums[k - 1] += nums[i];
for (int i = k; i < length; i++)
prefixSums[i] = prefixSums[i - 1] - nums[i - k] + nums[i];
int[][] dp = new int[length][n];
int[][] path = new int[length][n];
dp[k - 1][0] = prefixSums[k - 1];
path[k - 1][0] = k - 1;
for (int i = k; i < length; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i - 1][j];
path[i][j] = path[i - 1][j];
int prevSum = j == 0 ? prefixSums[i] : prefixSums[i] + dp[i - k][j - 1];
if (prevSum > dp[i][j]) {
dp[i][j] = prevSum;
path[i][j] = i;
}
}
}
int[] subarrays = new int[n];
int index = path[length - 1][n - 1];
subarrays[n - 1] = index - k + 1;
for (int i = n - 2; i >= 0; i--) {
index = path[index - k][i];
subarrays[i] = index - k + 1;
}
return subarrays;
}
}

• // OJ: https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& A, int k) {
int N = A.size(), M = N - k + 1, maxSum = 0;
vector<int> sum(M);
for (int i = 0, a = 0, b = 0; i < N; ++i) {
a += A[i];
if (i - k >= 0) b += A[i - k];
if (i - k + 1 >= 0) sum[i - k + 1] = a - b;
}
stack<int> s;
for (int i = M - 1; i >= 2 * k; --i) {
if (s.empty() || sum[i] >= sum[s.top()]) s.push(i);
}
vector<int> ans;
for (int i = k, left = 0; i < M - k; ++i) {
if (sum[i - k] > sum[left]) left = i - k;
int val = sum[left] + sum[i] + sum[s.top()];
if (val > maxSum) {
maxSum = val;
ans = {left, i, s.top()};
}
if (i + k == s.top()) s.pop();
}
return ans;
}
};

• class Solution:
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
s = s1 = s2 = s3 = 0
mx1 = mx12 = 0
idx1, idx12 = 0, ()
ans = []
for i in range(k * 2, len(nums)):
s1 += nums[i - k * 2]
s2 += nums[i - k]
s3 += nums[i]
if i >= k * 3 - 1:
if s1 > mx1:
mx1 = s1
idx1 = i - k * 3 + 1
if mx1 + s2 > mx12:
mx12 = mx1 + s2
idx12 = (idx1, i - k * 2 + 1)
if mx12 + s3 > s:
s = mx12 + s3
ans = [*idx12, i - k + 1]
s1 -= nums[i - k * 3 + 1]
s2 -= nums[i - k * 2 + 1]
s3 -= nums[i - k + 1]
return ans

############

class Solution(object):
def maxSumOfThreeSubarrays(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
N = len(nums)
sums = [0]
left = [0] * N
right = [N - k] * N
mx = 0
res = [0, 0, 0]
for i, num in enumerate(nums):
sums.append(sums[-1] + num)
total = sums[k] - sums[0]
for i in range(k, N):
if sums[i + 1] - sums[i - k + 1] > total:
left[i] = i - k + 1
total = sums[i + 1] - sums[i - k + 1]
else:
left[i] = left[i - 1]
total = sums[N] - sums[N - k]
for j in range(N - k - 1, -1, -1):
if sums[j + k] - sums[j] >= total:
right[j] = j
total = sums[j + k] - sums[j]
else:
right[j] = right[j + 1]
for i in range(k, N - 2 * k + 1):
l, r = left[i - 1], right[i + k]
total = (sums[i + k] - sums[i]) + (sums[l + k] - sums[l]) + (sums[r + k] - sums[r])
if total > mx:
mx = max(mx, total)
res = [l, i, r]
return res

• func maxSumOfThreeSubarrays(nums []int, k int) []int {
ans := make([]int, 3)
s, s1, s2, s3 := 0, 0, 0, 0
mx1, mx12 := 0, 0
idx1, idx121, idx122 := 0, 0, 0
for i := k * 2; i < len(nums); i++ {
s1 += nums[i-k*2]
s2 += nums[i-k]
s3 += nums[i]
if i >= k*3-1 {
if s1 > mx1 {
mx1 = s1
idx1 = i - k*3 + 1
}
if mx1+s2 > mx12 {
mx12 = mx1 + s2
idx121 = idx1
idx122 = i - k*2 + 1
}
if mx12+s3 > s {
s = mx12 + s3
ans = []int{idx121, idx122, i - k + 1}
}
s1 -= nums[i-k*3+1]
s2 -= nums[i-k*2+1]
s3 -= nums[i-k+1]
}
}
return ans
}