689. Maximum Sum of 3 Non-Overlapping Subarrays


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


    • Approach #1: Ad-Hoc [Accepted]

    Intuition

    It is natural to consider an array W of each interval's sum, where each interval is the given length K. To create W, we can either use prefix sums, or manage the sum of the interval as a window slides along the array.

    From there, we approach the reduced problem: Given some array W and an integer K, what is the lexicographically smallest tuple of indices (i, j, k) with i + K <= j and j + K <= k that maximizes W[i] + W[j] + W[k]?

    Algorithm

    Suppose we fixed j. We would like to know on the intervals and , where the largest value of (and respectively ) occurs first. (Here, first means the smaller index.)

    We can solve these problems with dynamic programming. For example, if we know that is where the largest value of occurs first on , then on the first occurrence of the largest must be either or . If say, is better, then we set best = 6.

    At the end, left[z] will be the first occurrence of the largest value of W[i] on the interval , and right[z] will be the same but on the interval . This means that for some choice j, the candidate answer must be (left[j-K], j, right[j+K]). We take the candidate that produces the maximum W[i] + W[j] + W[k].

    Complexity Analysis

    • Time Complexity: , where is the length of the array. Every loop is bounded in the number of steps by , and does work.

    • Space complexity: . W, left, and right all take memory.

    Analysis written by: @awice

    Submit Solution