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

isuch that 0 ≤iandi+k<nwe calculate the sumarr[i] +arr[i+ 1] + ... +arr[i+k- 1] and store it insum[i].Then we start iterating the

sumarray fromk'th index ton- 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 rangesum[0], ...,sum[i-k](this will be the first segment) and maximum sum from the rangesum[i+k], ...sum[n-k](this is the 3rd segment). But these are all prefix and suffixes of thesumarray. 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)