Practice/Meta/Leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays

Leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays

CodingMust

Problem

You are given an array of positive integers and a positive integer k. Your task is to find three non-overlapping contiguous subarrays, each of length k, such that the sum of all elements in these three subarrays is maximized.

Return the starting indices of these three subarrays in ascending order. If there are multiple valid solutions with the same maximum sum, return the lexicographically smallest tuple of indices.

Requirements

1. The three subarrays must not overlap with each other
2. Each subarray must have exactly k elements
3. The starting indices returned must be in ascending order
4. When multiple solutions yield the same maximum sum, choose the one with the smallest first index, then smallest second index, then smallest third index (lexicographically smallest)
5. The solution should run in O(n) time where n is the length of the input array

Constraints

• 1 <= nums.length <= 20000
• 1 <= nums[i] <= 65535
• 1 <= k <= floor(nums.length / 3)
• At least three non-overlapping subarrays of length k can always be formed

Examples

Example 1:

` Input: nums = [1, 2, 1, 2, 6, 7, 5, 1], k = 2 Output: [0, 3, 5] Explanation: The three subarrays are:

• [1, 2] starting at index 0 (sum = 3)
• [2, 6] starting at index 3 (sum = 8)
• [7, 5] starting at index 5 (sum = 12) Total sum = 23, which is maximum possible. `

Example 2:

` Input: nums = [4, 3, 2, 5, 1, 6], k = 1 Output: [0, 3, 5] Explanation: The three subarrays are:

• [4] at index 0
• [5] at index 3
• [6] at index 5 Total sum = 15 `

Example 3:

Input: nums = [1, 2, 1, 2, 1, 2, 1, 2, 1], k = 2 Output: [0, 2, 4] Explanation: Multiple solutions exist with the same sum, but [0, 2, 4] is lexicographically smallest.