使用遞歸在Java中進行最大子數組檢測

我正在嘗試在Java中使用遞歸實現最大子數組問題。使用遞歸在Java中進行最大子數組檢測

但我的代碼不斷拋出異常。我無法弄清楚是什麼導致了這個問題，我相信這可能是因爲遞歸的基本情況在第一次迭代時觸底。

感謝

import java.lang.*; 

    class Subarray{ 
     int low; 
     int high; 
     int sum; 


     Subarray MaxCrossSub(int a[], int low, int mid, int high) 
     { 
      Subarray sub=new Subarray(); 

      double leftsum=Double.NEGATIVE_INFINITY; 
      double rightsum=Double.NEGATIVE_INFINITY; 
      double sum=0; 
      int maxleft=0; 
      int maxright=0; 
      for(int i=mid;i>=low;i--) 
      { 
       sum=sum+a[i]; 
       if(sum>leftsum) 
       { 
        leftsum=sum; 
        maxleft=i; 
       } 

      } 

      sum=0; 
      for(int i=mid+1;i>=high;i++) 
      { 
       sum=sum+a[i]; 
       if(sum>rightsum) 
        rightsum=sum; 
        maxright=i; 

      } 


      sub.low=maxleft; 
      sub.high=maxright; 
      sub.sum=maxleft+maxright; 
      return sub; 
     } 
     Subarray MaxSub(int a[],int low,int high) throws Exception 
     { 
      Subarray leftsub=new Subarray(); 
      Subarray rightsub=new Subarray(); 
      Subarray crosssub=new Subarray(); 

      if(low==high) 
      { 
       leftsub.low=low; 
       leftsub.high=low; 
       leftsub.sum=a[low]; 
      } 
      int mid=(low+high)/2; 
      leftsub=MaxSub(a,low,mid); 
      rightsub=MaxSub(a,mid+1,high); 
      crosssub=MaxCrossSub(a,low,mid,high); 


      if(leftsub.sum>rightsub.sum && leftsub.sum>crosssub.sum) 
       return leftsub; 
      else if(rightsub.sum>leftsub.sum && rightsub.sum>crosssub.sum) 
      return rightsub; 
      else 
       return crosssub; 



     } 
    } 
    public class MaximumSubarray { 

    public static void main(String[] args) throws Exception { 

     Subarray sub=new Subarray(); 
     int a[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15-4,7}; 
     int low=0; 
     int high=16; 


     sub=sub.MaxSub(a,low,high); 

     System.out.println("low"+sub.low); 
     System.out.println("high"+sub.high); 
     System.out.println("Sum"+sub.sum); 






    } 
    }

來源

2017-01-29 Siddharth Bhardwaj

可以添加子陣最大的幾樣？ – Salman

說**我的代碼一直拋出異常**是不夠的。您還需要提供異常詳細信息。 –

你確定你MaxSub方法「拋出Exeption」有必要嗎？

來源

2017-01-29 12:50:03 busz

這必須是一個評論，而不是一個答案。 –

，你的問題是造成

 int mid=(low+high)/2; 
     leftsub=MaxSub(a,low,mid);

我不明白你願意當O（n）的算法可here實現這個算法的思想非遞歸結束。

它的Java版本將是這樣的：

static int max_subarray(int[] a){ 
     int max_ending_here = 0, max_so_far = 0; 

     for(int x : a){ 
      max_ending_here = Math.max(0, max_ending_here + x); 
      max_so_far = Math.max(max_so_far, max_ending_here); 
     } 
     return max_so_far; 
    }

來源

2017-01-29 13:43:18 Igor

使用遞歸在Java中進行最大子數組檢測

回答

相關問題