UVA, 10684 The jackpot

题意：首先输入一个N，代表后面N个继续输入的数字，求数字的最大子序列和

思路:动态规划，最大子序列和（最大子段和）

　　　　最大子序列和的转移方程：f[i]=max（f[i-1]+date[i],date[i])可以直接用……

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 int n,date[10000],f[10000];
 8 
 9 int cmp (const void *a,const void *b)
10 {
11     return *(int*)a-*(int*)b;
12 }
13 
14 bool datecin()
15 {
16     if(scanf("%d",&n)!=EOF&&n)
17     {
18         for(int i=0;i<n;i++)
19         {
20             scanf("%d",&date[i]);
21             f[i]=0;
22         }
23         return true;
24     }
25     return false;
26 }
27 
28 void showf()
29 {
30     for(int i=0;i<n;i++)
31         cout<<f[i]<<' ';
32     cout<<endl;
33 }
34 
35 void datecal()
36 {
37     f[0]=date[0];
38     for(int i=1;i<=n;i++)
39     {
40         if(f[i-1]>0)
41             f[i]=f[i-1]+date[i];
42         else
43         {
44             f[i]=date[i];
45         }
46     }
47     //showf();
48     qsort(f,n,sizeof(f[0]),cmp);//这里我直接用了qsort
49     //cout<<f[0]<<':'<<f[n-1]<<endl;
50 }
51 
52 void showres()
53 {
54     if(f[n-1]>0)
55         printf("The maximum winning streak is %d.
",f[n-1]);
56     else
57         printf("Losing streak.
");
58 }
59 int main()
60 {
61     while(datecin())
62     {
63         datecal();
64         showres();
65     }
66     return 0;
67 }

上面代码里使用了qsort函数，是一个排序挺方便的函数，先简单地用一下，后面仔细学习一下

最大子序列和也有多种解决方法，这里我用了动态规划，其他的方法，后面也写一个= =加入学习队列！orz