本文共 592 字，大约阅读时间需要 1 分钟。

Description

求最大连续子序列的和

Input

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

Output

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

Sample Input

６1 2 -5 6 7 8

Sample Output

21

思路

这道题不应该叫最长子串吗
这道题目符合最优子结构，可以用dp完成：
设b[i]为一直到i为止的一定要包括i的最长子串（即连续子序列）的和，那么：
$b[i]=max(b[i-1]+a[i],0)(1<=i<=n)$
dp，输出
贴代码：

#include<iostream>#include<algorithm>using namespace std;int u[600];int main(){   	int n,mx=0;	cin>>n;	for (int i=1;i<=n;i++)	{   		int x;		cin>>x;		if (u[i-1]+x<=0) u[i]=0;		else u[i]=u[i-1]+x;		mx=max(mx,u[i]);	}	cout<<mx;	return 0;}