划分型 DP

题目	难度
2478. 完美分割的方案数	困难	方案数
3077. K 个不相交子数组的最大能量值	困难	不 需要覆盖整个数组

模板

3077. K 个不相交子数组的最大能量值

public class Solution3077 {
    public long maximumStrength(int[] nums, int k) {
        int n = nums.length;
        long[] ps = new long[n + 1];
        for (int i = 0; i < n; i++) {
            ps[i + 1] = ps[i] + nums[i];
        }

        long[][] f = new long[k + 1][n + 1];
        for (int i = 1; i <= k; i++) {
            long w = (i % 2 > 0 ? 1 : -1) * (k - i + 1);

            long mx = Long.MIN_VALUE;
            f[i][i - 1] = mx;
            for (int j = i; j < n - k + i + 1; j++) {
//                for (int L = i - 1; L <= j - 1; L++) {
//                    mx = Math.max(mx, f[i - 1][L] + (ps[j] - ps[L]) * w);
//                }
                mx = Math.max(mx, f[i - 1][j - 1] - ps[j - 1] * w);

                f[i][j] = Math.max(f[i][j - 1], ps[j] * w + mx);
            }
        }
        return f[k][n];
    }
}

（全文完）