Kadane 算法实现 returns 不正确的结果

Question

我已经编写了 Kadane 的算法，但不知何故它 return 的结果不正确。不知道为什么。这是实现。基本上就是在一个array

中找到和最大的`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));
    }
}

我想它应该以某种方式 return 最大总和为 7。在计算中我看到正在计算 7 但它 return 1. 我在代码中缺少任何基本的东西吗？

我已经阅读了其他实现，它们也很有意义，只是我不明白为什么它不是 return 正确答案。

提前致谢！

Answer 1

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

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

Kadane 算法实现 returns 不正确的结果

Kadane algorithm implementation returns incorrect result

java

algorithm

kadanes-algorithm