3473. Sum of K Subarrays With Length at Least M

You are given an integer array nums and two integers, k and m.

Return the maximum sum of k non-overlapping subarrays of nums, where each subarray has a length of at least m.

c++

class Solution {
public:
    int maxSum(vector<int>& nums, int k, int m) {
        vector<vector<long long>> dp(k, vector<long long>(m+1, INT_MIN));
        dp[0][0] = 0;
        long long res = INT_MIN;
        for(auto& x : nums) {
            for(int i = k - 1; i >= 0; i--) {
                if(i) dp[i][0] = max(dp[i][0], dp[i-1][m]);
                dp[i][m] = max({dp[i][m] + x, dp[i][m-1] + x});
                for(int j = m - 1; j; j--) {
                    dp[i][j] = dp[i][j-1] + x;
                }
            }
            res = max(res, dp[k-1][m]);
        }
        return res;
    }
};