Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/689.html
689. Maximum Sum of 3 Non-Overlapping Subarrays
Level
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.lengthwill be between 1 and 20000.nums[i]will be between 1 and 65535.kwill 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 }