【C】课堂结对联系-求整数数组的子数组之和的最大值（党云龙、黄为）

• 测试题目
  求整数数组的子数组之和的最大值。
• 题目分析
  首先是明确题目的目的：求最大值；其次是考虑子数组求和。这里将求最大值写成一个单独的函数。主函数未测试函数。这里用到了二重循环，时间复杂度为N^2.
• 源代码分析
  
  

  #include"stdio.h"
  #define MAXSIZE 100
  
  
  /*int Max(int num[],int length)
  {
      int max=num[0];
      //int n;
      int sum=0;
      int flag=0;
      for(int j=0;j<length;j++)
          {
              if(max<num[j])
                  max=num[j];        
          }
      
  
      for(int k=0;k<length-1;k++)
          {
              if(max<(num[k]+num[k+1]))
                  max=(num[k]+num[k+1]);
  
          }
          for(int m=0;m<length-2;m++)
          {
              if(max<(num[m]+num[m+1]+num[m+2]))
                  max=(num[m]+num[m+1]+num[m+2]);
  
          }
          for(int n=0;n<length-3;n++)
          {
              if(max<(num[n]+num[n+1]+num[n+2]+num[n+3]))
                  max=(num[n]+num[n+1]+num[n+2]+num[n+3]);
  
          }
          for(int z=0;z<length-4;z++)
          {
              if(max<(num[z]+num[z+1]+num[z+2]+num[z+3]+num[z+4]))
                  max=(num[z]+num[z+1]+num[z+2]+num[z+3]+num[z+4]);
  
          }
          
          if(max<(num[0]+num[1]+num[2]+num[3]+num[4]+num[5]))
                  max=(num[0]+num[1]+num[2]+num[3]+num[4]+num[5]);
  
  
        
          return max;
  }*/
   int Max(int num[],int length)
   {
       int max=num[0];
       
       if(length<=0)
       {
           printf("数组个数为零或负数,错误，默认MAX设为0");
           return 0;
       }
       for(int k=0;k<length;k++)
       {
       if(num[k]==-858993460)
       {
           printf("数组含为NULL,错误，默认MAX设为0");
           return 0;
       }
       }
       for(int i=0;i<length;i++)
       {
           int sum=0;
           for(int j=i;j<length;j++)
           {
               sum+=num[j];
               if(max<sum)
                   max=sum;
           }
       }
       return max;
   }
  main()
  {
      //int num[]={-10,-12,1,-1,9,10};
      //int length=6;
      int num[MAXSIZE];
      int length;
      printf("输入数组个数：");
      scanf("%d",&length);
      for(int x=0;x<length;x++)
          scanf("%d",&num[x]);
      /*for(int i=0;i<6;i++)
      printf("%d  ",num[i]);*/
      printf("\n");
          
          printf("MAX:%d\n",Max(num,length));
  }

  

  这里我进行了一些异常情况的处理
  
  
  
  
  
  
  

• 上课思路
  
  
• 扩展-线性实现
  如何利用线性实现，首先要对整形数组进行分析：
  1、零对于和没有影响。
  2、数组是全负的情况(若只有负数和零，则max=0)
      

  for(int i=0;i<length;i++)
  {
      if(max<num[i])
          max=num[i];    
  }

  3、数组是全正的情况（含0）
   

  for(int i=0;i<length;i++)
  {
      if(max<num[i])
          max=num[i];    
  }

  4、有正有负的情况
       首先是要顺序寻找第一个大于零的整数，记录下来数组下标，然后接着寻找下一个负数，得到负数段，也求和，得到一段正数段，求和，按照这种方法遍历整个数组。
       对这些正数段与负数段进行判断与求和，从而实现求出最大者。

• 线性实现
       待下回分解！

  
  
  

【C】课堂结对联系-求整数数组的子数组之和的最大值（党云龙、黄为）,布布扣,bubuko.com

原文：http://www.cnblogs.com/feelwell/p/3592559.html