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

All Problems

All Solutions