java中的kadane算法

我在java中有以下Kadane算法的實現。基本上是找到連續子數組的最大總和。java中的kadane算法

String[] numbers = string.split(","); 
       int max_so_far = 0; 
       int max_ending_here = 0; 
       for (int i = 0; i < numbers.length-1;i++){ 
        max_ending_here = max_ending_here + Integer.parseInt(numbers[i]); 
        if (max_ending_here < 0) 
         max_ending_here = 0; 
        if (max_so_far < max_ending_here) 
          max_so_far = max_ending_here; 
       } 
       System.out.println(max_so_far);

然而，如果存在負和正數的在陣列中的組合，這並不工作，例如下列：

2,3,-2,-1,10

哪個應該返回一個12爲最大。到目前爲止，它返回5

來源

2011-08-29 aherlambang

這裏有什麼問題？你嘗試過調試嗎？ –

它現在給了什麼價值？ – luketorjussen

或者i <= numbers.length-1會更好地理解長度。 – Kunalxigxag

您的算法實現看起來不錯，但是您的循環條件爲i < numbers.length-1不會：它僅停止1個數組末尾。 i < numbers.length應該這樣做:-)

來源

2011-08-29 16:43:21 rsp

是的，這是一個愚蠢的錯誤..謝謝！它偶爾會發生一次 – aherlambang

這就是爲什麼每個循環都非常棒。你避免這樣的陷阱。 –

這個工作對我來說：

String string = "2,3,-2,-1,10"; 
    String[] numbers = string.split(","); 
    int max_so_far = 0; 
    int max_ending_here = 0; 
    for (String num : numbers) { 
     int x = Integer.parseInt(num); 
     max_ending_here = Math.max(0, max_ending_here + x); 
     max_so_far = Math.max(max_so_far, max_ending_here); 
    } 
    System.out.println(max_so_far);

來源

2011-08-29 16:53:29

關於上述答案由米哈爾Šrajer：

線＃7：max_ending_here = Math.max（0，max_ending_here + X ）;

應該是：

max_ending_here = Math.max（X，max_ending_here + X）;

...根據Kadane算法定義here

來源

2012-09-06 03:14:37

太晚了，但如果有人需要它的未來。

public static void kadaneAlgo(int[][] array) 
    for(int i = 1; i < array.length; i++){ 
      int max_value_index_i = numberOrSum(array[i], past); 
      if(max_value_index_i > sum){ 
       sum = max_value_index_i; 
      } 
      past = max_value_index_i; 

     } 
     System.out.println("Max sum from a contiguous sub array is : " + sum); 
    } 

    public static int numberOrSum(int number, int past){ 
     return Math.max(number, number+past); 
    }

來源

2017-10-14 06:38:38 Nishit

java中的kadane算法

回答

相關問題