Three Non-Overlapping Peak Traffic Windows
A traffic log records requests per minute. To provision three separate capacity reservations, pick three non-overlapping windows of equal length k that together capture the most traffic. Return the earliest such window starts.
Problem
Given an integer array nums and an integer k, find three non-overlapping subarrays each of length k with maximum total sum, and return their starting indices. If multiple answers tie, return the lexicographically smallest list of starting indices.
Input
An integer array nums of length n and an integer k with 1 <= 3k <= n.
Output
An array of three starting indices in increasing order.
Constraints
- 1 <= nums.length <= 2 * 10^4
- 1 <= k, and 3 * k <= nums.length
- 1 <= nums[i] < 2^16
Examples
Example 1
Input
nums = [1,2,1,2,6,7,5,1], k = 2
Output
[0,3,5]
Windows [1,2],[2,6],[7,5] sum to 3+8+12 = 23, the maximum.
Example 2
Input
nums = [1,2,1,2,1,2,1,2,1], k = 2
Output
[0,2,4]
Equal sums force the lexicographically smallest start triple.