功    能：   在一个整数序列中求一个子序列，该子序列的和最大   输入说明：   首先输入整数序列的长度 length               接着输入该整数序列            输出说明：   输出子序列的起点和终点，并输出该子序列的和        事    例：   (建议用管道测试)                        输入文件 data.txt  内容如下：                     8       12 -13 1 2 23 -14 55 -2                     输出：       The subsequence from 2 to 6,max sum is 67 （序列从1开始算） 评 价：  这个题可以有几种算法：o(n^3),o(n^2),o(nlogn),o(n)                本程序使用o(n)，这种求法几乎完美 ！     语    言：   非标准 C  编译环境：VC ++ 6.0              Author  ：   江南孤峰  Time ：2006--11--9       #include <stdio.h>#include <stdlib.h> #include <limits.h>#include <malloc.h> int main(){ int *ip; int j,length,max,sum; int start1 = 0 ,start2 = 0;  printf("Please enter the array's length:"); scanf("%d",&length); if((ip = (int*)malloc(length*sizeof(int)))==NULL){  fprintf(stderr,"Malloc memory failed !");  exit(1); } printf("Enter eath element:"); for(j = 0; j < length ; j ++)  scanf("%d",ip+j);  max = INT_MIN; for(sum = j = 0; j < length; j ++){  sum += *(ip+j);  if(max < sum){   start1 = start2;   max = sum;  }  if(sum < 0){   start2 = j+1;   sum = 0;  } } for(j = start1,sum = 0; sum != max; j ++)  sum += *(ip+j); printf("\nThe subsequence from %d to %d,max sum is %d\n",start1,j-1,max); return 0;} // 下面是网友的题目，估计也是ACM题，和上面的题差不多，所以贴这里算了 现的问题是如果求环形整数串的最大连续和子串呢？  输入数据 本题有多组输入数据，你必须处理到EOF为止 每组数据的第一行有一个整数n, (1<=n<=1000000).第2行有n个整数，每个整数都在[-100,100]的范围内 输出数据 每组数据输出一个整数，表示环形整数串最大连续子串和。 输入样例 6 -2 3 0 1 -48 80 2 1 3 5 10 -2 -3 1 1 输出样例 82 4 12  分析：环行的 数组其实可以看做将该数组写两次，不过为了节约空间，在达到数组长度时我们可以绕到数组的起始，下面的代码就是这样。ACM的题目都强调速度，如果下面的程序不能通过，可以尝试后面那个，空间换时间。这里时间复杂度都是O(n^2)。 代码一： #include <stdio.h>#include <stdlib.h>#include <malloc.h> #include <limits.h> int main(){ int *ip; int i,j,n,max,maxSave,sum;  while(scanf("%d",&n) != EOF){  if((ip = (int*)malloc(n*sizeof(int)))==NULL){   fprintf(stderr,"Malloc memory failed !");   exit(1);  }  for(j = 0; j < n ; j++)   scanf("%d",ip+j);  maxSave = INT_MIN;   for(i = 0; i < n; i++){   for(max = sum = *(ip+i),j = i+1;j != i; j++){    if(j == n){     j = -1;     continue;    }    sum += *(ip+j);    if(max < sum)     max = sum;    if(sum < 0)     sum = 0;   }   if(maxSave < max)    maxSave = max;  }  printf("%d\n",maxSave);  free(ip); } return 0;} 代码二： // 注意TC开不了这么大的数组#include <stdio.h> #include <limits.h> int a[2000000];int main(){ int i,j,n,max,maxSave,sum;  while(scanf("%d",&n) != EOF){  for(j = 0; j < n ; j++){   scanf("%d",&a[j]);   a[j+n] = a[j];  }  maxSave = INT_MIN;  for(i = 0; i < n; i++){   for(max = sum = 0,j = i;j < n+i; j++){    sum += a[j];    if(max < sum)     max = sum;    if(sum < 0)     sum = 0;   }   if(maxSave < max)    maxSave = max;  }  printf("%d\n",maxSave); } return 0;}  2007 ---- 8 ----- 28   更新[来自湖大ACM] [解题报告]： 作者：wation 解题思路： 首先考虑是否所有数据都不大于0，这种情况直接输出最大数（不证明）， 然后，分别求出非环串的最大子段和和最小子段和以及和， 结果等于max（最大子段和，和-最小子段和）； 证明： 设串s="s1,s2,...,sn" 构成最大子段和的串smax="si,si+1,...sk" 构成最小子段和的串smin="sj,sj+1,...sf" 首先证明smax和smin不存在公共子串。 证1：假设存在ssub="st,...sp"即属于smax，也属于smin； 首先假设ssub在smax中，必然存在smax-ssub<smax（smax-ssub表示smax中除掉ssub所构成的子串）， 推出ssub>0（ssub的所有元素之和大于0） 同理假设ssub在smin中推出ssub<0； 从而推出矛盾，所以smax和smin不存在公共子串。 然后证明smax和smin要么相邻要么中间存在一个和为0的子串。 证明2：要证上述结论只要证得在smax和smin不相邻的情况下 假设存在nsub="sk+1,...,sf-1"，使得nsub=0； 假设nsub>0，那么smax+nsub>smax，根据求解方法，smax必将扩充到sf-1；所以nsub<=0 同理推出nsub不能小于0； 所以推出nsub=0； 最后证明环串的最大子段和csmax=max(smax,s-smin); 证3：假设存在一个子串vsmax>csmax； 显然vsmax是两端两个子串的合并，否则必然有vsmax<=smax 设 vsmax="s1,...,sz"+"sx,...,sn" 那么sx一定>sf，因为如果假设sx<sf，即smin和vsmax存在公共子串，1已经证明不存在了； 再者sz一定小于si,如果sz>=si,根据求解方法vsmax必将继续扩展直到sz=sk， 因为"sf,...,sx"=0（2已经证得）,所以有vsmax=s-smin；与假设矛盾。 a、假设csmax=smax,那么vsmax>smax，即"s1,...,sz"+"sx,...,sn">"si,si+1,...sk", 即s-smin-"sz+1,...,si-1"-smax>"si,si+1,...sk", 即s-smin-"sz+1,...,si-1"-smax>smax既-"sz+1,...,si-1"-smax>smax-（s-smin）>0，因为那么根据求解思路smin应该 ="sz+1,...,sf"，所以矛盾 b、假设csmax=s-smin,那么vsmax>s-smin，既s-smin-"sz+1,...,si-1"-smax>s-smin,即-"sz+1,...,si-1"-smax>0, 同理得出矛盾。 从证1，证2，证3得证结论环串最优解等于max（最大子段和，和-最小子段和）； 至于求非环串最大最小子段和可以用dp算法。 下面是我根据上面思路写的代码：#include <iostream> using namespace std; int main(){     int n,i,amax,amin,submax,submin,sum,t;     for(;cin>>n;){         cin>>t;         sum = submin = amin = submax = amax = t;         for(i=1; i<n; i++){             cin>>t;             sum += t;             amax = amax>0 ? amax+t : t;             if(amax > submax)                 submax = amax;             amin = amin<0 ? amin+t : t;             if(amin < submin)                 submin = amin;         }         if(sum-submin > submax && sum!=submin)             cout<<(sum-submin)<<endl;         else             cout<<submax<<endl;     }     return 0;  } Language : GNU C++ , Judge Result: Time Limit Exceeded#include <stdio.h> int main(){     int n,i,amax,amin,submax,submin,sum,t;     for(;scanf("%d",&n)!=EOF;){         scanf("%d",&t);         sum = submin = amin = submax = amax = t;         for(i=1; i<n; i++){             scanf("%d",&t);             sum += t;             amax = amax>0 ? amax+t : t;             if(amax > submax)                 submax = amax;             amin = amin<0 ? amin+t : t;             if(amin < submin)                 submin = amin;         }         if(sum-submin > submax && sum!=submin)             printf("%d\n",sum-submin);         else             printf("%d\n",submax);     }     return 0;  } Language : GNU C , Judge Result: Accepted 296ms以C++方式提交 ： GNU C++Accepted984KB265ms510B比赛的时候稍微注意下。。。。。

评论