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.
Example 1:
Input: nums = [1,2,1,2,6,7,5,1], k = 2 Output: [0,3,5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically smaller.
Example 2:
Input: nums = [1,2,1,2,1,2,1,2,1], k = 2 Output: [0,2,4]
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i] < 2161 <= k <= floor(nums.length / 3)This approach uses a prefix sum array to quickly calculate the sum of any subarray and a sliding window technique to explore possible starting points for the subarrays.
This C solution uses three arrays:
prefix[] for prefix sums to compute subarray sums quickly.left[] to store the starting index of the max subarray sum from the left.right[] to store the starting index of the max subarray sum from the right.It iterates over potential middle subarray starting points and uses these auxiliary arrays to compute the total sum efficiently. Updates are made to get the largest sum and store associated index positions in result[].
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), since we make a constant number of passes through the array.
Space Complexity: O(n), due to the prefix, left, and right arrays.
This approach employs dynamic programming alongside a sliding window to optimize subarray sum calculations and ensure non-overlapping conditions.
This C solution introduces a dynamic programming table (dp) to record the maximum sum up to each point. Using left and right tracking, it determines the best left and right subarrays. A single pass checks for optimal middle subarrays using this dynamic information.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), for traversal of the nums array multiple times.
Space Complexity: O(n), utilizing the dp, prefix, left, and right arrays.
| Approach | Complexity |
|---|---|
| Prefix Sum with Sliding Window | Time Complexity: O(n), since we make a constant number of passes through the array. |
| Dynamic Programming with Sliding Window | Time Complexity: O(n), for traversal of the nums array multiple times. |
Maximum Sum of 3 Non-Overlapping Subarrays - Leetcode 689 - Python • NeetCodeIO • 11,532 views views
Watch 9 more video solutions →Practice Maximum Sum of 3 Non-Overlapping Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor