Maximum Sum of M Non-Overlapping Subarrays II
Problem
Given an integer array nums and integers m, l, r, select at least 1 and at most m non-overlapping subarrays, each with length in the range [l, r], so that the total sum of the chosen subarrays is maximized. Return that maximum total sum.
nums = [4,1,-5,2], m = 2, l = 1, r = 37[4,1] (sum 5) and [2] (sum 2). Both lengths lie in [1,3]; total 5 + 2 = 7.def maximumSum(nums, m, l, r):
n = len(nums)
NEG = float("-inf")
# prefix[i] = sum of the first i elements
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
# dp[j][i] = best total over the first i elements using exactly j subarrays
dp = [[NEG] * (n + 1) for _ in range(m + 1)]
for i in range(n + 1):
dp[0][i] = 0 # zero subarrays => sum 0
for j in range(1, m + 1):
for i in range(n + 1):
best = dp[j][i - 1] if i >= 1 else NEG # skip element i-1
for length in range(l, r + 1): # end a subarray at i
start = i - length
if start < 0:
break
if dp[j - 1][start] == NEG:
continue
cand = dp[j - 1][start] + prefix[i] - prefix[start]
best = max(best, cand)
dp[j][i] = best
return max(dp[j][n] for j in range(1, m + 1)) # at least one subarrayfunction maximumSum(nums, m, l, r) {
const n = nums.length;
const NEG = -Infinity;
// prefix[i] = sum of the first i elements
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
// dp[j][i] = best total over the first i elements using exactly j subarrays
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(NEG));
for (let i = 0; i <= n; i++) dp[0][i] = 0; // zero subarrays => sum 0
for (let j = 1; j <= m; j++) {
for (let i = 0; i <= n; i++) {
let best = i >= 1 ? dp[j][i - 1] : NEG; // skip element i-1
for (let len = l; len <= r; len++) { // end a subarray at i
const start = i - len;
if (start < 0) break;
if (dp[j - 1][start] === NEG) continue;
const cand = dp[j - 1][start] + prefix[i] - prefix[start];
best = Math.max(best, cand);
}
dp[j][i] = best;
}
}
let ans = NEG;
for (let j = 1; j <= m; j++) ans = Math.max(ans, dp[j][n]); // >= 1 subarray
return ans;
}long maximumSum(int[] nums, int m, int l, int r) {
int n = nums.length;
final long NEG = Long.MIN_VALUE / 4;
// prefix[i] = sum of the first i elements
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
// dp[j][i] = best total over the first i elements using exactly j subarrays
long[][] dp = new long[m + 1][n + 1];
for (long[] row : dp) java.util.Arrays.fill(row, NEG);
for (int i = 0; i <= n; i++) dp[0][i] = 0; // zero subarrays => sum 0
for (int j = 1; j <= m; j++) {
for (int i = 0; i <= n; i++) {
long best = i >= 1 ? dp[j][i - 1] : NEG; // skip element i-1
for (int len = l; len <= r; len++) { // end a subarray at i
int start = i - len;
if (start < 0) break;
if (dp[j - 1][start] == NEG) continue;
long cand = dp[j - 1][start] + prefix[i] - prefix[start];
best = Math.max(best, cand);
}
dp[j][i] = best;
}
}
long ans = NEG;
for (int j = 1; j <= m; j++) ans = Math.max(ans, dp[j][n]); // >= 1
return ans;
}long long maximumSum(vector<int>& nums, int m, int l, int r) {
int n = nums.size();
const long long NEG = LLONG_MIN / 4;
// prefix[i] = sum of the first i elements
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
// dp[j][i] = best total over the first i elements using exactly j subarrays
vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, NEG));
for (int i = 0; i <= n; i++) dp[0][i] = 0; // zero subarrays => sum 0
for (int j = 1; j <= m; j++) {
for (int i = 0; i <= n; i++) {
long long best = i >= 1 ? dp[j][i - 1] : NEG; // skip element i-1
for (int len = l; len <= r; len++) { // end a subarray at i
int start = i - len;
if (start < 0) break;
if (dp[j - 1][start] == NEG) continue;
long long cand = dp[j - 1][start] + prefix[i] - prefix[start];
best = max(best, cand);
}
dp[j][i] = best;
}
}
long long ans = NEG;
for (int j = 1; j <= m; j++) ans = max(ans, dp[j][n]); // >= 1 subarray
return ans;
}Explanation
We need to choose some non-overlapping subarrays — at least one, at most m — where each chosen piece has a length between l and r, and the sum of all chosen pieces is as large as possible. Because pieces cannot overlap and we process the array left to right, this is a clean dynamic-programming over prefixes problem.
First we build a prefix-sum array so the sum of any subarray nums[a .. b-1] is just prefix[b] − prefix[a] in O(1). That lets us add a whole subarray to a partial answer without re-scanning it.
The table dp[j][i] holds the best achievable total when we look only at the first i elements and have chosen exactly j subarrays. Row j = 0 is all zeros: using zero subarrays earns sum 0. Every other cell starts at −∞, meaning "not reachable yet".
To fill dp[j][i] we consider two moves. We can skip element i−1, inheriting dp[j][i−1]. Or we can end the j-th subarray exactly at index i: for each allowed length len in [l, r] we look back to start = i − len, take the best answer there with one fewer subarray dp[j−1][start], and add the subarray sum prefix[i] − prefix[start]. The best of all these options becomes dp[j][i].
Since the problem allows at most m subarrays but requires at least one, the answer is the best of dp[1][n], dp[2][n], …, dp[m][n]. Negative arrays are handled naturally: if every subarray sum is negative, the table still picks the single least-negative window.
On the constraint n ≤ 10⁵ the inner length loop is replaced by a sliding-window maximum (a monotonic deque) over the term dp[j−1][start] − prefix[start], and the count limit is handled with WQS binary search on a per-subarray penalty — but the recurrence above is exactly what those optimizations accelerate.