求最大字段和的二种算法

意思暴力法，穷举出各种字段和情况，求出结果，想法通俗易懂，就是效率太低了．

代码语言：javascript复制

package day20180506;
public class FileSum {

    public static void main(String[] args) {
        int[] arr= {1,-2,6,10,-8,9};
        int max=getMaxFile(arr);
    }
    
       static int  getMaxFile(int[] arr) {
           
           int max=0;
           int sum=0;
           for(int i=0; i<arr.length; i  )
           {
               for(int j=i; j<arr.length; j  )
               {
                   sum=getSum(arr,i,j);
                   if(sum>max) 
                    max=sum; 
               }     
           }   
        System.out.println("max=" max);
         return max;
     }
    
       static int getSum(int[] arr,int i,int j)
       {
           int sum=0;
          for(int n=i; n<=j; n  ) 
           sum =arr[n];
         return sum;
       }
    

}

代码语言：javascript复制

max=17

＞这个方法，靠理解了，就是分治法

代码语言：javascript复制

package day20180506;

public class GetFilemax {

    public static void main(String[] args) {
    
            int[] arr= {1,-2,6,10,-8,9};
            System.out.println("sum=" max(arr,0,arr.length-1));
    }
    
    public static int max(int[] arr,int left,int right)
    {
        int max=0,sum=0,midsum=0,leftsum=0,rightsum=0;
        int s1,s2,lefts,rights;
        int mid;
    //递归出口很重要
        if(left==right)
        {
            sum=arr[left];
        }else
        {
        //划分
        mid=(left right)/2;
        leftsum=max(arr,left,mid);  //左部和
        rightsum=max(arr,mid 1,right); //右部分和
        
        s1=0;lefts=0;
        //左部和
        for(int i=mid; i>=left; i--)
        {
            lefts =arr[i];
            if(lefts>s1)
            s1=lefts;
        }
        
        //右部分和
        s2=0; rights=0;
        for(int i=mid 1; i<=right; i  )
        {
            rights =arr[i];
            if(rights>s2)
            s2=rights;
        }
        
        midsum=s1 s2;
        if(midsum>leftsum)
            sum=midsum;
        else sum=leftsum;
        if(rightsum>sum)
            sum=rightsum;   
        }
        
    
        return sum;
    }

}

sum=17

sum 效率

0 人点赞