117. Maximum Sum of 3 Non-Overlapping Subarrays

Given an integer array nums and integer k, find three non-overlapping subarrays of length k with maximum sum. Return the starting indices of the three subarrays. If multiple answers exist, return the lexicographically smallest.

Input: Integer array nums and integer k.

Output: Array of 3 starting indices [i,j,l].

Examples

Input: [1,2,1,2,6,7,5,1],2
Output: [0,3,5]
Explanation: Subarrays [1,2],[2,6],[7,5] have sums 3,8,12. Total=23. Starting indices: 0,3,5.

Input: [1,2,1,2,1,2,1,2,1],2
Output: [0,2,4]
Explanation: Multiple valid, return lexicographically smallest.

Input: [1,2,3,4,5,6,7,8,9],3
Output: [0,3,6]
Explanation: Optimal: [1,2,3],[4,5,6],[7,8,9].

Constraints

• 1<=nums.length<=2*10^4
• 1<=nums[i]<2^16
• 1<=k<=floor(nums.length/3)

Asked by