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 contiguous subarrays that maximize the total sum.
**Constraints:**
-
\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. No other pair of two disjoint non-empty subarrays does better (for instance `[3, 5]` (sum 8) and `[4, -3, 2]` (sum 3) total only 11).
**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). Specify the DP transitions and handle edge cases ($K > $ number of positive segments, all-negative arrays). Output both the maximum total sum and the backtracked intervals.
Open the full interactive solver, hints, and worked solution →