Max Sum Plus Plus(DP + 最大子段和)

Max Sum Plus Plus

题目

link

给一个长n的序列，分成m段，求最大子段和。（各个子段不重叠）

思路

很显然要用dp写。
当以最右区间元素下标为标准 ，我们可以给出dp的朴素定义即
dp[i][j] 表示只考虑[1,j]的序列并把序列分为i组，且最右子段右端为a[j]的最大和

之后要么连接旧子段，要么开一个新子段：

dp[i][j] = max ( dp[i][j-1] + a[j] , dp[i-1][k] +a[j])
其中的 k 当 dp[i-1][k] 为最值时取到

按这种写法 ， O(mnn) 铁TL，空间也 可能炸 ，两方面都要优化。

1. 时间优化，由于每次用的有本层和上一层的数据，所以本层用01背包的方法优化掉，上一层的数据需要用一个pre_max记录。
2. 空间优化，压成1维，类比01背包优化。

这么说挺抽象的。。。具体还得看代码。

AC代码

明确mx和pre_max的定义后还是很好理解的，这种巧妙的优化很值得学习。

#include 
#define inf 0x3f3f3f3f
//#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 10 + 1e6;
int dp[N]; //
// dp[i][j] = max( dp[i][j-1]+a[j] , dp[i-1][k] + a[j]  )
// 考虑j个数 分为i组 且最后一个区段右端为a[j]
// 答案应当是dp[m] 中的最值
int a[N];
int pre_max[N]; //上层区段[i,n]中最大值
int n, m;
void solve()
{int mx = -inf;memset(dp, 0, sizeof dp);memset(pre_max, 0, sizeof pre_max);for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= m; i++){mx = -inf;for (int j = i; j <= n; j++){dp[j] = max(dp[j - 1], pre_max[j - 1]) + a[j];//使用上层最值pre_max[j - 1] = mx;//为下次迭代更新上层最值 mx = max(dp[j], mx);// mx 记录当前层[i,j]区段max 用做更新pre_max}}// int ans=-inf;// for(int i=m;i<=n;i++)//注意起始点//     ans=max(ans,dp[i]);// cout<cout << mx << endl;
}
int main()
{ios::sync_with_stdio();while (cin >> m >> n)solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！