我已经编写了 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。代码中是否缺少任何基本的东西?
我已经阅读了其他实现,它们也很有意义,只是没有弄清楚为什么它没有返回正确的答案。
提前致谢!
最佳答案
您没有考虑到您可能已经找到了您想要的金额这一事实。因此,您需要:
return Math.max(sum, Math.max(calculate(arr, pointer+1, sum+arr[pointer]), calculate(arr, pointer+1, 0)));
关于java - Kadane 算法实现返回错误结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59536713/