1043.md

1043 分隔数组以得到最大和

Solution 1

一维动态规划, 每个元素会和它前面的n个数组成一组, 时间复杂度: O(n * k).

class Solution {
    public int maxSumAfterPartitioning(int[] nums, int k) {
        int[] dp = new int[nums.length + 1];

        for (int r = 1; r <= nums.length; r++) {
            int maxNum = 0;
            for (int l = r; l > 0; l--) {
                maxNum = Math.max(maxNum, nums[l - 1]);
                if (r - l + 1 > k) {
                    break;
                }

                dp[r] = Math.max(dp[r], dp[l - 1] + (r - l + 1) * maxNum);
            }

        }

        return dp[nums.length];
    }
}