【每日一题Day182】LC1043分隔数组以得到最大和 | dp

分隔数组以得到最大和【LC1043】

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

二十分钟 满足了

• 思路
  使用动态规划，将前i个元素进行分割的最大和，可以枚举分割点由之前的状态转移得到，因此可以定义状态dp[i+1]为将前i个元素分隔变换后能够得到的元素最大和
• 明确 dp 函数/数组的定义。

定义状态dp[i+1]为将前i个元素分隔变换后能够得到的元素最大和

• 确定 base case，初始状态的值：dp[0]=0
• 确定「状态」，也就是原问题和子问题中会变化的变量。

    本题中状态为分隔变换后能够得到的元素最大和

• 确定「选择」，也就是导致「状态」产生变化的行为。

    第i个元素最长可以分割的子数组为nums[i−k+1:i]，因此可以枚举与nums[i]为一组的左端点j∈[i−k+1,i]，此时的最大和为将nums[0:j−1]进行分割的最大值nums[j:i]变换后的值之和

。实现时，使用变量记录当前子数组nums[j:i]中元素的最大值mx，于是可以得到状态转移方程

实现

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];       
        for (int i = 0; i < n; i++){
            int mx = arr[i];
            for (int j = i; j >= Math.max(0, i - k + 1); j--){
                mx = Math.max(mx, arr[j]);
                dp[i + 1] = Math.max(dp[i + 1], dp[j] + mx * (i - j + 1));
            }
        }
        return dp[n];
    }
}

复杂度

• 时间复杂度：O(nk)
• 空间复杂度：O(n)