3956. Maximum Sum of M Non-Overlapping Subarrays I

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.

class Solution {
    pair<long long, int> helper(vector<int>& nums, vector<long long>& pre, long long m, long long l, long long r,long long cost) {
        int n = nums.size();
        vector<long long> dp(n + 1);
        vector<int> cnt(n + 1);
        deque<int> dq;

        auto val = [&](int i) {
            return dp[i] - pre[i];
        };

        auto bad = [&](int a, int b) {
            long long va = val(a);
            long long vb = val(b);

            if (va != vb) return va < vb;
            return cnt[a] <= cnt[b];
        };

        for (int i = l; i <= n; i++) {
            int add = i - l;

                while (!dq.empty() and bad(dq.back(), add)) dq.pop_back();
                dq.push_back(add);

            while (!dq.empty() && dq.front() < i - r) dq.pop_front();

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

            if (!dq.empty()) {
                long long take = val(dq.front()) + pre[i] - cost;
                int takeCnt = cnt[dq.front()] + 1;

                if (take > dp[i] or (take == dp[i] and takeCnt > cnt[i])) {
                    dp[i] = take;
                    cnt[i] = takeCnt;
                }
            }
        }

        return {dp[n], cnt[n]};
    }
public:
    long long maximumSum(vector<int>& nums, int m, int l, int r) {
        long long n = nums.size(), res = LLONG_MIN;
        vector<long long> pre(n + 1);
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
        {
            multiset<long long> ms;
            for(int i = n - l; i >= 0; i--) {
                ms.insert(pre[i+l]);
                res = max(res, *prev(end(ms)) - pre[i]);
                if(i + r <= n) ms.erase(ms.find(pre[i+r]));
            }
        }
        auto zero = helper(nums, pre, m, l, r, 0);
        if(!zero.second) return res;
        if(zero.second <= m) return zero.first;
        long long le = 0, ri = 1e18;
        while (le <= ri) {
    long long mid = le + (ri - le) / 2;
    auto [v, c] = helper(nums, pre, m, l, r, mid);

    if (c > m) {
        le = mid + 1;
    } else {
        ri = mid - 1;
    }
}

auto [v, c] = helper(nums, pre, m, l, r, ri);

return v + ri * 1LL * m;
    }
};