Maximum Sum of 3 Non-Overlapping Subarrays

In a given arraynumsof positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of sizek, and we want to maximize the sum of all3*kentries.

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

分析

Thought process:

Dynamic programming.

1. Create an array of sums of windows of size k. This array's length will be nums.length - k + 1, because an array can have this many choices of windows.
2. Iterate through the windows and find the index of the window with the max sum to the left and to the right.
3. Iterate through the windows again and get and three windows with max sum.