Maximum Sum of 3 Non-Overlapping Subarrays — LeetCode 689 Python Solution
HardArrayDynamic ProgrammingPrefix SumSliding Window
- Problem
- #689
- Pattern
- Sliding Window
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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).
Example
- 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].
Python solution
Python
class Solution:
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
s = s1 = s2 = s3 = 0
mx1 = mx12 = 0
idx1, idx12 = 0, ()
ans = []
for i in range(k * 2, len(nums)):
s1 += nums[i - k * 2]
s2 += nums[i - k]
s3 += nums[i]
if i >= k * 3 - 1:
if s1 > mx1:
mx1 = s1
idx1 = i - k * 3 + 1
if mx1 + s2 > mx12:
mx12 = mx1 + s2
idx12 = (idx1, i - k * 2 + 1)
if mx12 + s3 > s:
s = mx12 + s3
ans = [*idx12, i - k + 1]
s1 -= nums[i - k * 3 + 1]
s2 -= nums[i - k * 2 + 1]
s3 -= nums[i - k + 1]
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the array nums |
| Space | O(1) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays?
- LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays is rated Hard on LeetCode.
- What is the time complexity of LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays?
- The Python solution on this page runs in O(n), where n is the length of the array nums.
- What is the space complexity of LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays cover?
- LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays is tagged Array, Dynamic Programming, Prefix Sum and Sliding Window on LeetCode.