Notebook

3956. Maximum Sum of M Non-Overlapping Subarrays I

From O(m·n³) brute-force DP to O(m·n) using prefix sums and a monotonic deque to track the best subarray starts in a sliding window.

4 min read DPPrefix SumMonotonic Deque

Problem Statement

You are given an integer array nums of length n, and three integers m, l, and r.

Your task is to select at least one and at most m non-overlapping subarrays from nums such that:

  • Each selected subarray has a length between [l, r] (inclusive).
  • The total sum of all selected subarrays is maximized.

Return the maximum total sum you can achieve.

Examples

Example 1

Input: nums = [4,1,-5,2], m = 2, l = 1, r = 3
Output: 7

Explanation: Select the subarray [4, 1] with sum 4 + 1 = 5 and the subarray [2] with sum 2. Both subarrays have length between [l, r]. The total sum is 5 + 2 = 7.

Example 2

Input: nums = [1,0,3,4], m = 2, l = 1, r = 2
Output: 8

Explanation: Select the subarray [1] with sum 1 and the subarray [3, 4] with sum 3 + 4 = 7. The total sum is 1 + 7 = 8.

Example 3

Input: nums = [-1,7,-4], m = 1, l = 2, r = 3
Output: 6

Explanation: Select the subarray [-1, 7] which has sum -1 + 7 = 6.

Example 4

Input: nums = [-3,-4,-1], m = 2, l = 1, r = 2
Output: -1

Explanation: All subarrays have negative sums. The optimal strategy is to select [-1].

Constraints

  • 1 <= n == nums.length <= 1000
  • -10^9 <= nums[i] <= 10^9
  • 1 <= m <= n
  • 1 <= l <= r <= n

Explanation

  • we need to pick at least 1 subarray and at most m
  • each of the picked subarrays’ length should be in [l, r]

let’s start with our DP approach:

dp[i][k][j] = maximum possible sum if we pick i subarrays and the current subarray starts at k and ends at j

so for each i from 1...m
    for each k from 1....n
        for each j from 1...n
            we have options like skip j (don't end subarray now)
            dp[i][k][j] = dp[i-1][k][j]
            end subarray at j such that (j-k >= l and j-k <= r) // size should be in range [l,r]
            dp[i][k][j] = max(dp[i][k][j], dp[i-1][k][j] + sum(nums[k..j]))

this solution is O(m·n³). using prefix sum we can compute the range sum in O(1):

dp[i][k][j] = max(dp[i][k][j], dp[i-1][k][j] + prefix[j] - prefix[k-1])

it’s still not fast enough to pass since m <= 1000 and n <= 1000, so our solution is O(m·n²).

but if we look carefully we don’t need to maintain all the starting points (k). we can maintain the best k values in a window of length [l, r] and pick the best starting point from there.

to maintain the best values in the window we can use a monotonic deque, which maintains the best values of subarrays with size at least l and at most r. this reduces an O(n) factor and our overall solution becomes O(m·n), which is fast enough for the given constraints.

Code

#define ll long long
class Solution {
public:
    long long maximumSum(vector<int>& nums, int m, int l, int r) {

        int n = nums.size();
        vector<vector<ll>> dp(m + 1, vector<ll>(n + 1, -4e18));
        vector<ll> pre(n + 1);

        for (int i = 0; i < n; i++)
            pre[i + 1] = pre[i] + nums[i];
        
        for (int i = 0; i <= n; i++)
            dp[0][i] = 0;

        for (int i = 1; i <= m; i++) {
            deque<ll> dq;

            for (int j = 1; j <= n; j++) {

                dp[i][j] = dp[i][j - 1];

                if (j - l >= 0) {
                    
                    ll x = dp[i - 1][j - l] - pre[j - l];
                    while (!dq.empty() and (dp[i - 1][dq.back()] - pre[dq.back()]) <= x) {
                        dq.pop_back();
                    }
                    dq.push_back(j-l);
                    
                }
                while (!dq.empty() and dq.front() < j - r)
                    dq.pop_front();
                
                if (!dq.empty())
                    dp[i][j] = max(dp[i][j], dp[i - 1][dq.front()] + pre[j] - pre[dq.front()]);
            }
        }

        ll ans = -4e18;
        for (int i = 1; i <= m; i++) {
            ans = max(ans, dp[i][n]);
        }
        return ans;
    }
};

Resources