。。。2012年5月9日。。。
//HDOJ登不上、暴力应该不能AC吧~不过我已经想好了怎么用逆推优化了~嘿嘿
。。。2012年5月10日。。。
//HDOJ还是登不上，把优化代码写好了，O(N)时间复杂度。逆推的~
。。。2012年5月11日。。。
//原来以前做过这题。http://www.cnblogs.com/CheeseZH/archive/2012/03/14/2397044.html
=================================================================================================
数组a用来存储输入的n个数
数组b用来存储当前位置所能取得的最大子串和值
数组c用来存储使b取得最大子串和的的终止位置（若ci=j，则是bi取得最大的子串和为i...j）
//暴力求解~#include <stdio.h> #define N 100001 int a[N],b[N],c[N]; int main() { int n,cas,i,j,k; int tsum,tmax,ti,tj; scanf("%d",&cas); for (i=1;i<=cas;i++) { scanf("%d",&n); for (j=0;j<n;j++) { scanf("%d",&a[j]); b[j]=0; c[j]=0; } tmax=0; for (j=0;j<n;j++) { tsum=0; for (k=j;k<n;k++) { tsum+=a[k]; if(tsum>b[j]) { b[j]=tsum; c[j]=k; } } if(b[j]>tmax) { tmax=b[j]; ti=j; tj=c[j]; } } printf("Case %d:\n",i); printf("%d %d %d\n",tmax,ti+1,tj+1); if(i!=cas) printf("\n"); } }
//优化的代码~
例如：按i=6..0的顺序推导哦~
i 0 1 2 3 4 5 6
a 0 6 -1 1 -6 7 -5
b 7 7 1 2 1 7 -5
c 5 5 5 5 5 5 6
只要用一个tmax和ti，tj记住最大的子串和就可以了~
Problem : 1003 ( Max Sum ) Judge Status : AcceptedRunId : 5922042 Language : C Author : qq1203456195Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta #include <stdio.h> #define N 1000005 int a[N],b[N],c[N]; int main() { int n,cas,i,j,tsum,tmax,ti,tj; // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); scanf("%d",&cas); for (i=1;i<=cas;i++) { scanf("%d",&n); for (j=0;j<n;j++) scanf("%d",&a[j]); c[n-1]=n-1; b[n-1]=a[n-1]; //注意tmax，ti，tj初始化 tmax=a[n-1]; ti=tj=n-1; for (j=n-2;j>=0;j--) { if(b[j+1]>0) {//这里不能是>= b[j]=a[j]+b[j+1]; c[j]=c[j+1]; }else{ b[j]=a[j]; c[j]=j; } if(b[j]>=tmax){ tmax=b[j]; ti=j; tj=c[j]; } } printf("Case %d:\n",i); printf("%d %d %d\n",tmax,ti+1,tj+1); if(i!=cas) printf("\n"); } }
转载于:https://www.cnblogs.com/CheeseZH/archive/2012/05/09/2493509.html
相关资源：数据结构—成绩单生成器