1043. 分隔数组以得到最大和 - Java 动态规划

原题地址：https://leetcode.cn/problems/partition-array-for-maximum-sum/

题解

参照官方题解思路

设dp[i]为子数组arr[0]——arr[i]的分割最大和，当我们遍历到i时，假设存在一个子数组arr[j]——arr[i]，则有：

• 该子数组的长度：length=i-j+1且满足i-j+1<=k
• 该子数组的最大和：maxsum(j,i)=max(arr[j],…,arr[i])*(i-j+1)
• 这种情况下的分割最大和为dp[j-1]+maxsum(j,i)
  • 即子数组arr[0]——arr[j-1]的分割最大和加上子数组arr[j]——arr[i]的最大和
• j从i开始倒叙遍历，一直遍历至j==0或者i-j+1>k为止，就是所有的子情况
  • 所有子情况下分割最大和的最大值即为dp[i]

时间复杂度：O(N^2)

空间复杂度：O(N)

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