Show problems as
Classic problem #689HardArrayDynamic ProgrammingSliding WindowPrefix Sum

Maximum Sum of 3 Non-Overlapping Subarrays

Real-world version: Three Blocks on the Support Rota
Tracked in this browser only
Read Maximum Sum of 3 Non-Overlapping Subarrays on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A support desk has an hour-by-hour record of how many calls arrived, given as nums, so nums[i] is the call count for hour i.

The rota needs three shifts, each covering exactly k consecutive hours. No hour may belong to two shifts, and the shifts are reported in the order they occur.

Return the three starting hours as a list [a, b, c] with a + k <= b and b + k <= c, chosen so that the total call count across the three shifts is as large as it can be.

Several triples may reach that largest total. In that case return the smallest triple when the three lists are compared entry by entry: the smallest a, then among those the smallest b, then among those the smallest c.

Examples

Example 1

Input
nums = [1, 10, 10, 1, 1, 2, 2, 1, 1, 10, 10, 1], k = 2
Output
[1, 5, 9]

The shifts start at hours 1, 5 and 9. Each covers two hours, hour 1 does not reach hour 5 and hour 5 does not reach hour 9, so nothing overlaps. Their call counts are 20, 4 and 20, a total of 44.

Example 2

Input
nums = [3, 1, 3, 1, 3, 1, 3], k = 1
Output
[0, 2, 4]

With one-hour shifts the counts picked are 3, 3 and 3, a total of 9. Other triples also reach 9, and comparing them entry by entry makes [0, 2, 4] the smallest.

Example 3

Input
nums = [4, 4, 4, 4, 4, 4, 4, 4, 4], k = 3
Output
[0, 3, 6]

Every hour has the same count, so any three three-hour shifts total 36. Only one arrangement fits nine hours, and it starts at 0, 3 and 6.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_sum_of_three_subarrays(nums: list[int], k: int) -> list[int]:
Java
public int[] maxSumOfThreeSubarrays(int[] nums, int k)

More on the same topics