UVA, 507 Jill Rides Again

题意：首先输入N，表示接下来N组数据，再输入M，表示每组数据有M-1个数字，求数字最大子序和，而且打印出其起点和终点.

思路：动态规划，最大子序和

该题和 UVA, 10684 The jackpot 相似，只是多加了一个查找起点终点操作和输入数字的变化。

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 using namespace std;
  6 
  7 int n,m,date[20005],f[20005];//数组大小要够，不然WA
  8 int st[20005],be,fi;//(╯‵□′)╯︵┻━┻我一开始就WA了
  9 
 10 
 11 void showf()
 12 {
 13     cout<<"f:";
 14     for(int i=0;i<m;i++)
 15         cout<<f[i]<<'	';
 16     cout<<endl;
 17 }
 18 void showst()
 19 {
 20     cout<<"st:";
 21     for(int i=0;i<m;i++)
 22         cout<<st[i]<<'	';
 23     cout<<endl;
 24 }
 25 //showf 和showst函数是我用来查看f和st数组中元素
 26 
 27 int findm(int l)//用于查找起点
 28 {
 29     int be;//= =这里一开始忘加了，弄得被修改了好多次，找了半天
 30     for(int i=l;i>0;i--)
 31     {
 32         if(st[i]<0)
 33             break;
 34         be=i;
 35     }
 36     return be;
 37 }
 38 void datecal(int k)
 39 {
 40     memset(f,0,sizeof(f));
 41     f[0]=date[0];
 42     int maxn=0;
 43     for(int i=1;i<=m;i++)
 44     {
 45         if(f[i-1]>=0)
 46         {
 47             st[i-1]=i-1;
 48             f[i]=f[i-1]+date[i];
 49         }
 50         else
 51         {
 52             f[i]=date[i];
 53             st[i-1]=-1;
 54         }
 55     }
 56     //showf();showst();
 57     for(int i=0;i<=m;i++)
 58     {
 59         if(maxn<f[i])
 60         {
 61             maxn=f[i];
 62             fi=i;
 63         }
 64     }
 65 
 66     if(maxn!=0)
 67     {
 68         be=findm(fi);
 69         //cout<<fi<<':'<<be<<endl;
 70         for(int i=0;i<=m;i++)
 71         {
 72             if(maxn==f[i]&&i!=fi)//进行长度比较
 73             {
 74                 int temp=fi+1-be;
 75                 int fil=i;
 76                 int bel=findm(i);
 77                 int temq=fil-bel;
 78                 if(i!=m)temq++;
 79                 if(temq>temp)
 80                 {
 81                    fi=fil;
 82                     be=bel;
 83                 }
 84             }
 85         }
 86         if(fi!=m)fi++;
 87             printf("The nicest part of route %d is between stops %d and %d
",k,be,fi);
 88     }
 89         else
 90             printf("Route %d has no nice parts
",k);
 91 }
 92 
 93 
 94 int main()
 95 {
 96     scanf("%d",&n);
 97     int k=1;
 98     for(int i=0;i<n;i++)
 99     {
100         scanf("%d",&m);
101         memset(date,0,sizeof(date));
102         date[0]=0;
103         for(int j=1;j<m;j++)
104         {
105             scanf("%d",&date[j]);
106             //cout<<date[j]<<endl;
107         }
108         datecal(k);
109         k++;
110 
111     }
112     return 0;
113 }

该题需注意同一大小的子序和,选择长度较大的