Maximum Sum of 3 Non-Overlapping Subarrays

Problem Description

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them. 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.

Key Insights

• The problem requires finding three non-overlapping subarrays of fixed length k.
• The sum of the selected subarrays should be maximized.
• We need to consider the lexicographical order of indices when multiple combinations yield the same sum.
• Dynamic programming can be employed to optimize the selection of subarrays.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will use a dynamic programming approach combined with a sliding window technique:

1. Calculate Subarray Sums: First, compute the sums of all possible subarrays of length k using a sliding window to keep track of the sum efficiently.

2. Dynamic Programming Arrays:

   • Use two arrays, left and right, where:
     • left[i] holds the maximum sum of a subarray ending at index i and the starting index of that subarray.
     • right[i] holds the maximum sum of a subarray starting at index i and the starting index of that subarray.

3. Maximize Total Sum: Iterate through possible middle subarrays (from k to n - 2k) and calculate the total sum for selecting a left subarray, the middle subarray, and a right subarray.

4. Return Indices: Track the indices of the chosen subarrays to return the lexicographically smallest solution.

Code Solutions