java - Kadane 算法实现返回错误结果

Question

我已经编写了 Kadane 算法，但不知何故它返回了错误的结果。不知道为什么。这是实现。基本上是在数组中找到“和最大的 ubarray”

public class Kadane {

    public static void main(String[] args) {
        int[] arr =  {-2, -5, 6, -2, -3, 1, 5, -6};
        Kadane k = new Kadane();
        System.out.println(k.calculate(arr, 0, 0));
    }

    public int calculate(int[] arr, int pointer, int sum) {
        if(pointer >= arr.length )
            return sum;

        return Math.max(calculate(arr, pointer+1, sum+arr[pointer]), calculate(arr, pointer+1, 0));
    }
}

我想它应该以某种方式返回最大和，即 7。在计算中，我看到正在计算 7，但它返回 1。代码中是否缺少任何基本的东西？

我已经阅读了其他实现，它们也很有意义，只是没有弄清楚为什么它没有返回正确的答案。

提前致谢!

Answer 1

您没有考虑到您可能已经找到了您想要的金额这一事实。因此，您需要:

return Math.max(sum, Math.max(calculate(arr, pointer+1, sum+arr[pointer]), calculate(arr, pointer+1, 0)));