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;
    }
}

All Problems

All Solutions