K Disjoint Maximum-Sum Subarrays
Given an array $a_1, a_2, \ldots, a_n$ of integers (possibly negative) and an integer $K \geq 1$, select $K$ non-overlapping non-empty contiguous subarrays that maximize the total sum. Return the maximum total sum as an integer.
Implement the function with signature:
```python def max_k_subarray_sum(a, K): ... ```
where a is the list of integers and K is the number of subarrays to select.
Constraints: - $1 \leq K \leq n$ - $-10^9 \leq a_i \leq 10^9$ - Subarrays must be non-empty and non-overlapping (disjoint)
Example 1: Input: a = [1, -2, 3, 5, -1, 4, -3, 2], K = 2 Output: 13 Explanation: Take [3, 5, -1, 4] (sum 11) and [2] (sum 2), for a total of 13.
Example 2: Input: a = [-1, -2, -3], K = 1 Output: -1 Explanation: Must select at least one subarray; the maximum single element is -1.
Design an $O(nK)$-time, $O(n)$-space algorithm (using rolling arrays). Handle edge cases ($K$ larger than the number of positive segments, all-negative arrays).
Example
max_k_subarray_sum([10, -1, 10], 2) -> 20
The two disjoint subarrays [10] and [10] (skipping the -1 gap) sum to 20; merging them into one subarray would incur the -1 and only give 19.
Hints
- Generalize Kadane's algorithm: at each position, you are either inside the $j$-th subarray or in a gap. Define two DP states accordingly.
- The transition for "inside subarray $j$ ending at position $i$" is: $\texttt{end}[j] = \max(\texttt{end}[j], \texttt{gap}[j-1]) + a_i$ -- either extend the current subarray or start a new one from the gap state.
- Process $j$ from $K$ down to 1 in the inner loop (like the 1D knapsack trick) to use rolling arrays and achieve $O(K)$ space for the value computation.
Worked Solution
How to Think About It: This extends Kadane's algorithm (maximum subarray, $K = 1$) to $K$ disjoint subarrays. At each position $i$ you are in one of two states: either the $j$-th subarray currently *ends* at $i$, or the $j$ completed subarrays all end at or before $i$. This gives a 2-state DP.
Algorithm:
Define two rolling arrays over positions: - cur[j] = max sum using exactly $j$ subarrays where the $j$-th subarray ends exactly at the current position - best[j] = max sum using exactly $j$ subarrays where all $j$ subarrays end at or before the current position
Transitions (processing each element $x = a_i$, iterating $j$ from $K$ down to $1$ so that best[j-1] still holds the previous position's value):
$$\texttt{cur}[j] = \max(\texttt{cur}[j],\; \texttt{best}[j-1]) + x$$
Either extend the current $j$-th subarray, or start a fresh $j$-th subarray here on top of $j-1$ finished ones.
$$\texttt{best}[j] = \max(\texttt{best}[j],\; \texttt{cur}[j])$$
Close (or keep) the $j$-th subarray at the current position.
Base cases: best[0] = 0, all other entries $-\infty$.
Final answer: best[K] after processing all $n$ elements. Return the integer total sum (not the intervals).
Code:
```python def max_k_subarray_sum(a, K): # Max total sum of K non-overlapping non-empty contiguous subarrays. n = len(a) INF = float('inf') # cur[j] = best sum with j subarrays, j-th subarray ends exactly at current position # best[j] = best sum with j subarrays, all ending at or before current position cur = [-INF] * (K + 1) best = [-INF] * (K + 1) best[0] = 0 for x in a: # iterate j high->low so best[j-1] still refers to previous position for j in range(K, 0, -1): cur[j] = max(cur[j], best[j - 1]) + x best[j] = max(best[j], cur[j]) return best[K] ```
Complexity: Time $O(nK)$ (outer loop over $n$, inner over $K$); space $O(K)$ with rolling arrays.
Edge cases: - All-negative array: works correctly — it selects the $K$ least-negative singletons, so the answer can be negative (e.g. [-1,-2,-3], K=1 -> -1). - $K = n$: every element becomes its own subarray, answer = sum of all elements. - $K = 1$: reduces to Kadane's algorithm.
Intuition
This problem generalizes the classic maximum subarray (Kadane's algorithm) to multiple disjoint subarrays. The key modeling insight is that you need two states per subarray count: "currently building" and "in a gap." The transition between these states captures the decision to start, extend, or close a subarray.
The $O(nK)$ complexity comes from the fact that for each of $n$ positions, you make a constant-time decision for each of $K$ subarray slots. The rolling-array trick (processing $j$ in reverse) collapses the space from $O(nK)$ to $O(K)$ for the value computation, just like in the 0-1 knapsack optimization. In practice, this pattern appears in portfolio optimization when selecting $K$ non-overlapping trading windows to maximize cumulative P&L, or in signal processing when isolating $K$ bursts of activity in a noisy time series.