AOJ 807 最长子序列和

本文主要是介绍AOJ 807 最长子序列和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面：

Description
给一串整数a[1..n]，求出其和最大的子序列，即找出1<=i<=j<=n（1<=n<=50000），使a[i]+a[i+1]+…+a[j]最大。

Input
多组输入，EOF结束，每组输入包含两行，第一行有一个数字n表示有n个数字，第二行有n个数字，每个数字的绝对值小于1000。

Output
对于每组输入，输出最大子序列和

Sample Input
5
2 -3 -5 7 6
5
1 4 6 -9 10

Sample Output
13
12

大体思路

动态规划的简单应用。状态转移方程：
dp[i]=max(dp[i-1]+dp[i],dp[i])

代码

#include<iostream>
#include<cstring>
using namespace std;
int dp[50010];
int max(int a,int b)//想着自己写max能快一点，没想到差不多··
{return a>b?a:b;
}
int main()
{int n;while(cin>>n){memset(dp,0,sizeof(dp));int Max=-10000;for(int i=1;i<=n;++i){cin>>dp[i];dp[i]=max(dp[i-1]+dp[i],dp[i]);Max=max(dp[i],Max);}cout<<Max<<endl;}return 0;
}

这篇关于AOJ 807 最长子序列和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---