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。我在代码中遗漏了什么基本的东西吗？

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

提前致谢！

标签： javaalgorithmkadanes-algorithm

Answer 1

您没有考虑到您可能已经找到了您想要的金额。因此，您需要：

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