最大子列.txt

来自「中过科学技术大学历年复试机试题」· 文本 代码 · 共 63 行

#include<stdio.h>
#include<stdlib.h>

#define N 10

void main(){//其实这里有一个规律，就是对于一个序列来说，如果一个子序列的和是最大的，
	        //那么这个子序列它的开头任意项的和不为负，从后往前算起的任意项的和也不为负。
	        //所以，如果当一个序列的和为负，那么它肯定就不会出现在和为最大的子序列中，
	        //这里，可以把i直接跳过这个序列，这样line_max的时间复杂度会降成O(n)，同理，
	        //一个矩阵也是这样。顺着这个思想做下去，应该可以把时间复杂度降下来的。
	        //不过具体怎么样，要想想才知道。对于一个序列求最大子序列可以这样做：
  int a[10];
  FILE *fp,*fpp;
  
  if((fp=fopen("e:\\yt\\yt01.txt","r"))==NULL){
      printf("file open error!\n");
      exit(0);
  }
  
  if((fpp=fopen("e:\\yt\\yt02.txt","a"))==NULL){
      printf("file open error!\n");
      exit(1);
  }

   //如果一个子序列的和是最大的，那么这个子序列它的开头任意项的和不为负，
   //从后往前算起的任意项的和也不为负。
  int i,j;
  int e,s,curSum,maxSum=0;
  while(!feof(fp)){
     for(i=0;i<N;i++){
       fscanf(fp,"%d",&a[i]);
	   fgetc(fp);
	 }
      
	 curSum=0;
	 maxSum=0;  

     for(i=0,j=0;j<N;j++){
	     curSum+=a[j];
		 if(curSum>maxSum){
		    s=i;
			e=j;
            maxSum=curSum;		 
		 }
		 else if(curSum<0){
		       i=j+1;
		       curSum=0;
		 }
	 
	 }
	 for(i=s;i<=e;i++){
	   fprintf(fpp,"%d ",a[i]);
       printf("%d ",a[i]);
	 }
	 fprintf(fpp,"\n s=%d  e=%d maxSum=%d \n",s,e,maxSum);
     printf("\n s=%d  e=%d maxSum=%d \n",s,e,maxSum);
    
  }

  fclose(fp);
  fclose(fpp);

}