首页 > 代码库 > hdu1087 最大递增子段和
hdu1087 最大递增子段和
http://acm.split.hdu.edu.cn/showproblem.php?pid=1087
状态方程:sum[j]=max{sum[i]}+a[j]; 其中,0<=i<=j,a[i]<a[j]
把当前最大和更新到数组中，注意顺序。
Input
Input contains multiple test cases. Each test case is described in a line as follow:
N value_1 value_2 …value_N
It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output
For each case, print the maximum according to rules, and one line one case.
Sample Input
3 1 3 2
4 1 2 3 4
4 3 3 2 1
0
Sample Output
4
10
3
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define INF 0xfffffffint a[1005];int dp[1005];int main(){ int n; while(scanf("%d",&n)==1 && n) { for(int i=1; i<=n; i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); int ans; for(int i=1; i<=n; i++) { ans=-INF; for(int j=0; j<i; j++) if(a[i]>a[j]) ans=max(ans,dp[j]); dp[i]=ans+a[i]; } ans=-INF; for(int i=1; i<=n; i++) ans=max(ans,dp[i]); printf("%d\n",ans); } return 0;}
hdu1087 最大递增子段和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。