最大连续数列的和

Description

求最大连续子序列的和

Input

第一行输入n(n<=500),第二行为n个以空格分开的整数(-1000到1000之间)；

Output

该序列中最大的连续子序列的和

Sample Input

6
1 2 -5 6 7 8

Sample Output

21

解题思路

这道题其实就是从从前往后加，如果现在的数加上前面的数小于0，就将这个数赋值为0，最后再在这个数列里找出最大值。
状态转移方程:
i f ( a [ i ] + f [ i − 1 ] < 0 ) f [ i ] = 0 ; e l s e f [ i ] = a [ i ] + f [ i − 1 ] ; if(a[i]+f[i-1]<0) { f[i]=0; } else f[i]=a[i]+f[i-1]; if(a[i]+f[i−1]<0)f[i]=0;elsef[i]=a[i]+f[i−1];

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int maxn=0,a[100010],n,m,f[100010];
int main()
{
   
	cin>>n;
	for(int i=1;i<=n;i++)
	 cin>>a[i];
	f[1]=a[1];
	for(int i=2;i<=n;i++)
	{
   
		if(a[i]+f[i-1]<0) //注意，这里是加f[i-1]，不然会错
		{
   
			f[i]=0;
		}
		else f[i]=a[i]+f[i-1];//加上上一个数
	}
	for(int i=1;i<=n;i++)
	 if(f[i]>maxn) maxn=f[i];//找出最大值
	cout<<maxn;
	return 0;
}