LeetCode 0689. Maximum Sum of 3 Non-Overlapping Subarrays Solution in Java, C++, Python & More | Explanation + Code

Description

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

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 1:

Input: nums = [1,2,1,2,6,7,5,1], k = 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.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
Output: [0,2,4]

 

Constraints:

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] < 216
• 1 <= k <= floor(nums.length / 3)

Solutions

Solution 1: Sliding Window

We use a sliding window to enumerate the position of the third subarray, while maintaining the maximum sum and its position of the first two non-overlapping subarrays.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

PythonJavaC++GoTypeScript

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(code-box)

class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int[] ans = new int[3]; int s = 0, s1 = 0, s2 = 0, s3 = 0; int mx1 = 0, mx12 = 0; int idx1 = 0, idx121 = 0, idx122 = 0; for (int i = k * 2; i < nums.length; ++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 = new 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; } }(code-box)

class Solution { public: vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) { vector<int> ans(3); int s = 0, s1 = 0, s2 = 0, s3 = 0; int mx1 = 0, mx12 = 0; int idx1 = 0, idx121 = 0, idx122 = 0; for (int i = k * 2; i < nums.size(); ++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 = {idx121, idx122, i - k + 1}; } s1 -= nums[i - k * 3 + 1]; s2 -= nums[i - k * 2 + 1]; s3 -= nums[i - k + 1]; } } return ans; } };(code-box)

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 }(code-box)

function maxSumOfThreeSubarrays(nums: number[], k: number): number[] { const n: number = nums.length; const s: number[] = Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } const pre: number[][] = Array(n) .fill([]) .map(() => new Array(2).fill(0)); const suf: number[][] = Array(n) .fill([]) .map(() => new Array(2).fill(0)); for (let i = 0, t = 0, idx = 0; i < n - k + 1; ++i) { const cur: number = s[i + k] - s[i]; if (cur > t) { pre[i + k - 1] = [cur, i]; t = cur; idx = i; } else { pre[i + k - 1] = [t, idx]; } } for (let i = n - k, t = 0, idx = 0; i >= 0; --i) { const cur: number = s[i + k] - s[i]; if (cur >= t) { suf[i] = [cur, i]; t = cur; idx = i; } else { suf[i] = [t, idx]; } } let ans: number[] = []; for (let i = k, t = 0; i < n - 2 * k + 1; ++i) { const cur: number = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]; if (cur > t) { ans = [pre[i - 1][1], i, suf[i + k][1]]; t = cur; } } return ans; }(code-box)

Solution 2: Preprocessing Prefix and Suffix + Enumerating Middle Subarray

We can preprocess to get the prefix sum array s of the array nums, where s[i] = ∑_{j=0}^{i-1} nums[j]. Then for any i, j, s[j] - s[i] is the sum of the subarray [i, j).

Next, we use dynamic programming to maintain two arrays pre and suf of length n, where pre[i] represents the maximum sum and its starting position of the subarray of length k within the range [0, i], and suf[i] represents the maximum sum and its starting position of the subarray of length k within the range [i, n).

Then, we enumerate the starting position i of the middle subarray. The sum of the three subarrays is pre[i-1][0] + suf[i+k][0] + (s[i+k] - s[i]), where pre[i-1][0] represents the maximum sum of the subarray of length k within the range [0, i-1], suf[i+k][0] represents the maximum sum of the subarray of length k within the range [i+k, n), and (s[i+k] - s[i]) represents the sum of the subarray of length k within the range [i, i+k). We find the starting positions of the three subarrays corresponding to the maximum sum.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

PythonJavaC++Go

class Solution: def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]: n = len(nums) s = list(accumulate(nums, initial=0)) pre = [[] for _ in range(n)] suf = [[] for _ in range(n)] t = idx = 0 for i in range(n - k + 1): if (cur := s[i + k] - s[i]) > t: pre[i + k - 1] = [cur, i] t, idx = pre[i + k - 1] else: pre[i + k - 1] = [t, idx] t = idx = 0 for i in range(n - k, -1, -1): if (cur := s[i + k] - s[i]) >= t: suf[i] = [cur, i] t, idx = suf[i] else: suf[i] = [t, idx] t = 0 ans = [] for i in range(k, n - 2 * k + 1): if (cur := s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]) > t: ans = [pre[i - 1][1], i, suf[i + k][1]] t = cur return ans(code-box)

class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length; int[] s = new int[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } int[][] pre = new int[n][0]; int[][] suf = new int[n][0]; for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) { int cur = s[i + k] - s[i]; if (cur > t) { pre[i + k - 1] = new int[] {cur, i}; t = cur; idx = i; } else { pre[i + k - 1] = new int[] {t, idx}; } } for (int i = n - k, t = 0, idx = 0; i >= 0; --i) { int cur = s[i + k] - s[i]; if (cur >= t) { suf[i] = new int[] {cur, i}; t = cur; idx = i; } else { suf[i] = new int[] {t, idx}; } } int[] ans = new int[0]; for (int i = k, t = 0; i < n - 2 * k + 1; ++i) { int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]; if (cur > t) { ans = new int[] {pre[i - 1][1], i, suf[i + k][1]}; t = cur; } } return ans; } }(code-box)

class Solution { public: vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) { int n = nums.size(); vector<int> s(n + 1, 0); for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } vector<vector<int>> pre(n, vector<int>(2, 0)); vector<vector<int>> suf(n, vector<int>(2, 0)); for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) { int cur = s[i + k] - s[i]; if (cur > t) { pre[i + k - 1] = {cur, i}; t = cur; idx = i; } else { pre[i + k - 1] = {t, idx}; } } for (int i = n - k, t = 0, idx = 0; i >= 0; --i) { int cur = s[i + k] - s[i]; if (cur >= t) { suf[i] = {cur, i}; t = cur; idx = i; } else { suf[i] = {t, idx}; } } vector<int> ans; for (int i = k, t = 0; i < n - 2 * k + 1; ++i) { int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0]; if (cur > t) { ans = {pre[i - 1][1], i, suf[i + k][1]}; t = cur; } } return ans; } };(code-box)

func maxSumOfThreeSubarrays(nums []int, k int) (ans []int) { n := len(nums) s := make([]int, n+1) for i := 0; i < n; i++ { s[i+1] = s[i] + nums[i] } pre := make([][]int, n) suf := make([][]int, n) for i, t, idx := 0, 0, 0; i < n-k+1; i++ { cur := s[i+k] - s[i] if cur > t { pre[i+k-1] = []int{cur, i} t, idx = cur, i } else { pre[i+k-1] = []int{t, idx} } } for i, t, idx := n-k, 0, 0; i >= 0; i-- { cur := s[i+k] - s[i] if cur >= t { suf[i] = []int{cur, i} t, idx = cur, i } else { suf[i] = []int{t, idx} } } for i, t := k, 0; i < n-2*k+1; i++ { cur := s[i+k] - s[i] + pre[i-1][0] + suf[i+k][0] if cur > t { ans = []int{pre[i-1][1], i, suf[i+k][1]} t = cur } } return }(code-box)