【算法导论】最大子数组——暴力求解

1. 暴力方法求解最大子数组问题：求出所有子数组的和并比较；

2. 伪代码

FIND-MAXIMUM- SUBARRAY(A)
    max  = - ∞
      for  i =  1   to A.length
          sum  =  0 
         for  j =  i to A.length
              sum  +=  A[j]
              if   sum  >  max
                max  =  sum  
                low  =  i
                high  =  j
    return (low, high, max) 

3. 代码实现

java

 public   class   MaxArray {

      private   static   class   Result {
          int   low;
          int   high;
          int   sum;

          public  Result( int  low,  int  high,  int   sum) {
              this .low =  low;
              this .high =  high;
              this .sum =  sum;
        }
    }

      static  Result findMaximumSubarray( int  [] A){
          int  max =  Integer.MIN_VALUE;
          int  low = 0 ;
          int  high = 0 ;
          for  ( int  i = 0; i < A.length; i++ ) {
              int  sum = 0 ;
              for  ( int  j = i; j < A.length; j++ ) {
                sum  +=  A[j];
                  if  (sum >  max) {
                    max  =  sum;
                    low  =  i;
                    high  =  j;
                }
            }
        }
          return   new   Result(low, high, max);
    }
} 

python

之前用切片其实也是暴力求解

 def   find_maximum_subarray1(nums):
    max_sum  = -float( '  inf  '  )
    result  =  {}
      for  i  in   range(len(nums)):
        total  =  0
          for  j  in   range(i, len(nums)):
              print  (j)
            total  +=  nums[j]
              if  total >  max_sum:
                max_sum  =  total
                result[  "  low  " ] =  i
                result[  "  high  " ] =  j
    result[  "  sum  " ] =  max_sum
      return  result

C语言

typedef  struct   {
      int   low;
      int   high;
      int   sum;
} result;

result find_maximum_subarray(  int  arr[],  int   len)
{
      int  max = -((unsigned)(~ 0 ) >>  1  );
      int   low, high, i, j;
      for  (i =  0 ; i < len; i++ )
    {
          int  sum =  0  ;
          for (j = i; j < len; j++ )
        {
            sum  +=  arr[j];
              if  (sum >  max)
            {
                max  =  sum;
                low  =  i;
                high  =  j;
            }
        }
    }
    result re;
    re.low  =  low;
    re.high  =  high;
    re.sum  =  max;
      return   re;
} 

 

查看更多关于【算法导论】最大子数组——暴力求解的详细内容...