luoguP1115 最大子段和

题目描述

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

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n个整数，第 i个整数表示序列的第 i个数字 ai 。

输出格式

输出一行一个整数表示答案。

输入样例

7

2 -4 3 -1 2 -4 3

输出样例

4

思路

将前n项累加，若大于0，则继续。否则从0开始，因为求最大子段和，如果前面的是负数，加上后一个数会是后一个数变小

代码

#include<bits/stdc++.h>
using namespace std;

int n;

long int _max(long int a[])
{
	long int x=0;
	long int s=-1e5;
	for(int i=1;i<=n;i++)
	{
		x=x>0?x+a[i]:a[i];
		s=max(s,x);
	}
	return s;
}

int main()
{
	cin>>n;
	long int a[200005];
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cout<<_max(a);
}
           

也可以用DP做

转移方程 f[i]=max(w[i],w[i]+f[i-1])

#include<bits/stdc++.h>
using namespace std;

long long int w[200001];
long long int f[200001];

int main()
{
	int n;
	scanf("%d",&n);
	long long int ans=-1e8;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&w[i]);
		f[i]=max(w[i],w[i]+f[i-1]);
		ans=max(ans,f[i]);
	} 
	printf("%lld",ans);
	return 0;
}