Maximum Sum of M Non-Overlapping Subarrays II - Solution & Explanation

Problem Overview: Given an array, you must select m non-overlapping subarrays so that the total sum is maximized. Each subarray must occupy a distinct range, so once you pick a segment, its indices cannot be reused by another segment.

Approach 1: Brute Force Enumeration (O(n^3 * m) time, O(m) space)

The most direct idea is to try every possible subarray as the first segment, then recursively search for the next non-overlapping segment to the right. For each start index i, iterate over all end indices j, compute the subarray sum, and repeat the process for the remaining m-1 segments. Even with prefix sums to compute range sums in O(1), the nested enumeration leads to extremely high complexity. This approach is mostly useful for understanding the constraint that each choice splits the array into independent regions.

Approach 2: Dynamic Programming with Prefix Sums (O(n * m) time, O(n * m) space)

The key observation: the optimal answer for the first i elements using k subarrays depends on either skipping index i or ending a subarray at i. Use a DP table dp[i][k] representing the maximum sum using the first i elements with k chosen segments. Prefix sums allow constant-time subarray sum queries. While iterating through the array, track the best candidate start using a running maximum so you can efficiently extend segments ending at i. This transforms the brute-force search into a linear scan per subarray count.

Approach 3: Space-Optimized DP (O(n * m) time, O(n) space)

The full DP table can be reduced because each layer k depends only on the previous layer k-1. Maintain two arrays: one for the previous subarray count and one for the current count. As you iterate through indices, update the running best value representing the best place to start a new segment. The logic mirrors the classic maximum subarray extension technique from dynamic programming combined with prefix sums. This version is typically the most practical implementation.

Recommended for interviews: The dynamic programming approach with prefix sums is what interviewers expect. Starting with the brute-force explanation shows you understand the combinatorial structure of choosing segments. Transitioning to dp[i][k] demonstrates the ability to convert exponential exploration into a structured DP solution. Strong candidates also mention the space optimization and explain how prefix sums remove repeated subarray calculations.