|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 |
#include <stdio.h>#include<stdlib.h>//最大子序列和问题，动态规划，公式为d(n)=max{d(n-1),0}+A[i]typedef
long long ll;ll number[1000001];int n;ll d[1000001]={0};ll max(ll a,ll b){ return
(a<b)? b:a;}int
main(){ int
i,j; while(scanf("%d",&n)!=EOF) { d[0]=0; scanf("%lld",&number[1]); ll m=number[1]; for(i=2;i<=n;i++) { scanf("%lld",&number[i]); if(number[i]<m) m=number[i]; } ll s=m; for(i=1;i<=n;i++) { d[i]=max(0,d[i-1])+number[i]; if(d[i]>s) s=d[i]; } printf("%lld\n",s); } return
0;} |
原文：http://www.cnblogs.com/wickedpriest/p/3601012.html