洛谷p1115 最大子段和

题目链接：###

题目分析：###

动态规划O(n)求解，设f[i]表示以i为终点的最大子段和

分两种情况：

若f[i-1]>0，则显然f[i]=f[i-1]+a[i]（a[i]必须包含在内）
若f[i-1]<=0，则f[i]=a[i]（加上f[i-1]只会让答案更小，对答案没有贡献）

扫一遍就好了，好像有别的一大堆做法（线段树？）不过这个比较优秀

代码：###

#include<bits/stdc++.h>

#define MAXN (200000+5)

using namespace std;

inline int read(){

    int f=1,cnt=0;char c;

    c=getchar();

    while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}

    while(isdigit(c)){cnt=cnt*10+c-'0';c=getchar();}

    return cnt*f;

}

int n;

int a[MAXN],f[MAXN];

int ans=-20000;

int main(){

	n=read();

	for(register int i=1;i<=n;i++)

		a[i]=read(),f[i]=a[i];

	f[0]=0;

	for(register int i=1;i<=n;i++){

		if(f[i-1]>0)f[i]=f[i-1]+a[i];

		if(f[i-1]<=0)f[i]=a[i];

		ans=max(ans,f[i]);

	}

	printf("%d",ans);

	return 0;

}

巴特西

洛谷p1115 最大子段和

题目链接：###

题目分析：###

代码：###

最新文章

热门文章