Sum of K Subarrays With Length at Least M - Solution & Explanation

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.