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应该这样做:-)