DP题：分隔数组以得到最大和

青旅半醒 2023-10-06 09:56 7阅读 0赞

## DP题：分隔数组以得到最大和 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]

#### 思路： ####

当遇到第i个数时，它是自己一组，还是和前1个数一组？… …还是和前k-1个数一组？

dp\[i\] 表示划分了前 i 个数字产生的最大和。这里的 i 下标从 1 开始。  
转移时，考虑第 i 个数字与之前多少个数字组成一个子数组。故枚举 j 从 1 到 K，取 dp(i−j)+max∗j 的最大值。这里的 max 为区间的最大值，可以在枚举转移的时候更新。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

递推方程：  
![在这里插入图片描述][20200528112621672.png]

#### 代码： ####

class Solution {
        
    public:
        int maxSumAfterPartitioning(vector<int>& A, int K) {
        
            int dp[501]={
        0};
            int i;
            int j;
            int maxx;
            for( i=1;i<=A.size();i++ )
            {
           
                maxx=-1;
                for( j=1;j<=K && i-j>=0;j++ )
                {
        
                    maxx=max( maxx,A[i-j] );   
                    dp[i]= max( dp[i],dp[i-j]+j*maxx );
                }
            }
            return dp[ A.size() ];
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200528110823802.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200528112248644.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20200528112621672.png]: https://img-blog.csdnimg.cn/20200528112621672.png