java - java中的kadane算法

Question

我在 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

Answer 1

您的算法实现看起来不错，但您的循环条件i < numbers.length-1不行：它仅在距离数组末尾不到 1 处停止。i < numbers.length应该这样做:-)

Answer 2

这对我有用：

    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);

Answer 3

关于 Michał Šrajer 的上述回答：

第 7 行：max_ending_here = Math.max(0, max_ending_here + x);

应该：

max_ending_here = Math.max(x, max_ending_here + x);

...根据此处定义的 Kadane 算法

Answer 4

为时已晚，但如果将来有人需要它。

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);
    }