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算法

回答

相关问题