Sum of K Subarrays With Length at Least M - Video Solutions
3473. Sum of K Subarrays With Length at Least M | Top-Down | Bottom Up DP | Bottom Up Optimised
Sum of K Subarrays With Length at Least M - Video Solution
Watch 5 video solutions for Sum of K Subarrays With Length at Least M, a medium level problem involving Array, Dynamic Programming, Prefix Sum. This walkthrough by Aryan Mittal has 3,193 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer array nums and two integers, k and m.
Return the maximum sum of k non-overlapping subarrays of nums, where each subarray has a length of at least m.
Example 1:
Input: nums = [1,2,-1,3,3,4], k = 2, m = 2
Output: 13
Explanation:
The optimal choice is:
- Subarray
nums[3..5]with sum3 + 3 + 4 = 10(length is3 >= m). - Subarray
nums[0..1]with sum1 + 2 = 3(length is2 >= m).
The total sum is 10 + 3 = 13.
Example 2:
Input: nums = [-10,3,-1,-2], k = 4, m = 1
Output: -10
Explanation:
The optimal choice is choosing each element as a subarray. The output is (-10) + 3 + (-1) + (-2) = -10.
Constraints:
1 <= nums.length <= 2000-104 <= nums[i] <= 1041 <= k <= floor(nums.length / m)1 <= m <= 3
Approach Overview
Problem Overview: You are given an array and must choose exactly k non-overlapping subarrays. Each chosen subarray must have length at least m. The goal is to maximize the total sum of all selected subarrays.
Approach 1: Brute Force Enumeration (Exponential)
Generate all possible subarrays of length ≥ m and try every combination of k non‑overlapping ones. For each valid set, compute the total sum and track the maximum. Prefix sums can speed up subarray sum calculation, but the number of combinations still grows exponentially. Time complexity is roughly O(n^k) in the worst case with O(n) auxiliary space for prefix sums. This approach only works for very small arrays and mainly helps understand the search space.
Approach 2: Dynamic Programming with Prefix Sums (O(n²k))
Use prefix sum to compute any subarray sum in O(1). Define dp[i][j] as the maximum sum using j valid subarrays considering the first i elements. For every ending index i, iterate over all possible starting points t where the subarray length is at least m. Update dp[i][j] = max(dp[i][j], dp[t-1][j-1] + sum(t..i)). This guarantees non-overlapping segments because the previous state ends before t. Time complexity is O(n²k) and space complexity is O(nk). It works but becomes slow when n grows.
Approach 3: Optimized DP with Rolling Best (O(nk))
The inner loop from the previous approach can be optimized by maintaining the best candidate transition. Rearranging the recurrence: dp[i][j] = prefix[i] + max(dp[t-1][j-1] - prefix[t-1]), where t ≤ i-m+1. As you iterate i, track the maximum value of dp[t-1][j-1] - prefix[t-1] for all valid starts. This eliminates the need to scan every possible t. Each index is processed once per k, resulting in O(nk) time and O(nk) space. This technique combines array iteration with dynamic programming and prefix sums.
Recommended for interviews: The optimized dynamic programming approach is what interviewers typically expect. Starting with the O(n²k) DP shows you understand the state transition. Reducing it to O(nk) by maintaining a running best value demonstrates strong DP optimization skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | Exponential (≈O(n^k)) | O(n) | Understanding the problem or verifying small test cases |
| DP with Prefix Sums | O(n²k) | O(nk) | Straightforward DP formulation when constraints are moderate |
| Optimized DP with Running Best | O(nk) | O(nk) | Optimal solution for large arrays; typical interview expectation |