最大子段和

发布时间:2023年12月25日

给出一个长度为 n n n 的序列 a a a,选出其中连续且非空的一段使得这段和最大。

如果均为负数,则输出 0 0 0

分析

考虑 dp

状态

d p i dp_i dpi? 为以 i i i 结尾的最大子段和。

状态转移方程

有两种方案:

  • 可以自己成为一个最大子段和,就是 a i a_i ai?
  • 可以跟前面的最大子段和拼起来,就是 d p i ? 1 + a i dp_{i-1}+a_i dpi?1?+ai?

两者取最大值。

答案循环找最大值即可。

代码

#include <bits/stdc++.h>
#define inf LONG_LONG_MAX
#define int long long 

using namespace std;

const int N = 5 * 1e5 + 5;

int n, a[N], dp[N], maxn = -inf;

signed main(){
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		dp[i] = a[i];//初始状态
	}
	for(int i = 2; i <= n; i ++){
		dp[i] = max(dp[i], dp[i - 1] + a[i]);
		maxn = max(maxn, dp[i]);
	}
	if(maxn < 0){
		cout << 0;
	}else{
		cout << maxn;
	}
  return 0;
}

文章来源:https://blog.csdn.net/zc2000911/article/details/135209563
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。