求子序列和最大

功    能：   在一个整数序列中求一个子序列，该子序列的和最大  
 输入说明：   首先输入整数序列的长度 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
#include

#include   //INT_MIN来源于此
#include

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){    //遇到了 正数，或者sum由负数变为了0
   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
#include
#include

#include

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

#include

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推出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再者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 
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>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)<
Language : GNU C++ , Judge Result: Time Limit Exceeded
#include 

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; i0 ? 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++
Accepted
984KB
265ms
510B
比赛的时候稍微注意下。。。。。