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).
Firstly, for every position of the array i such that 0 ≤ i and i + k < n we calculate the sum arr[i] + arr[i + 1] + ... + arr[i + k - 1] and store it in sum[i].
Then we start iterating the sum array from k'th index to n - 2k'th index and we assume that it is the middle segment of the 3 segments. Now all we have to do is to find the maximum sum from the range sum[0], ..., sum[i - k](this will be the first segment) and maximum sum from the range sum[i + k], ...sum[n - k](this is the 3rd segment). But these are all prefix and suffixes of the sum array. So we can pre-calculate the maximum sums in the prefix and suffix and use them here. Finally we just take the maximum from all of the total sums we found. Now the problem asks about the indexes. So we just keep track of the index in our calculation.
Overall complexity: O(n)