google 2009笔试题-最大子数组问题

ubuntuer

#include stdio.h>
#include stdlib.h>
void count_max_subarray(int A[], int n)
{
  int i;
  int sum = 0;
  int max = 0;
  int start = 0;
  int end = 0;
  
  int last_start;
  int last_end;
  
  for(i=0;in;i++)
   {
     sum += A;
     end++;
     if(sum > max)
      {
       max = sum;
       last_start = start;
       last_end = end;
      }
     else if(sum  0)
     {
       sum = 0;
       start = i + 1;
       end = i + 1;
      }
   }
   printf("max is %d\n", max);
   
   
   for(i=last_start;ilast_end;i++)
    {
     //p[i-last_start] = A;
     printf("%d\t",A);
   }
   
   printf("\n");
}
int main(int argc, char *argv[])
{
  int A[8] = {1,5,-2,-1,1,3,1,-2};
  int i;
  
  count_max_subarray(A, 8);
  system("PAUSE");   
  return 0;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76292/showart_2031927.html