Leetcode 3473

Link: https://leetcode.cn/problems/sum-of-k-subarrays-with-length-at-least-m

题目要求

给你一个整数数组 nums 和两个整数 k 和 m。
返回数组 nums 中 k 个不重叠子数组的最大和，其中每个子数组的长度至少为 m。

核心算法和原理

区间划分型DP，状态转移略

Essentials:

i 的左边界和右边界自己动手算，以及记得每次开始新的内层循环时，dp[m * j - 1]都先置INT_MIN / 2
最核心的是mx的优化：mx表示 l from (m * (j-1)) → (i - m) 中 (dp[l] - prefix[l]) 的最大值，而i from m * j，此时m * (j-1) == i - m，故可以在遍历i的时候就更新mx，而非常规区间DP中那样再来一层循环获取这个mx

代码


class Solution {
public:
    int maxSum(vector<int>& nums, int k, int m) {
        int n = nums.size();
        vector<int>prefix(n + 1);
        vector<int>dp(n + 1);
        vector<int> f(n + 1);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        for (int j = 1; j <= k; j++) {
            int mx = INT_MIN;

            // maintain mx
            for (int i = 0; i <= n; i++) {
                f[i] = dp[i] - prefix[i];
            }
            dp[m * j - 1] = INT_MIN / 2;
            for (int i = j * m; i <= n - m * (k - j); i++) {
                // i从这里开始的时候，恰好(i-m) == (m*(j-1))满足条件，
                // 所以直接线性维护mx就好了
                // tmp都直接省了，dp[l][j - 1]在循环外的f的更新中已被记录
                mx = max(mx, f[i - m]);
                dp[i] = max(dp[i - 1], prefix[i] + mx);
            }
        }
        return dp[n];
    }
};