下面是代碼片段：看到子陣列的最大和是 6，但它被計算為 7。
所以 Kadane 的演算法在這里失敗了？！
public class KadaneAlgo {
public static void main(String[] args) {
int maxSUm = maxSumSubArray(new int []{2,2,2,-2,-2,3,2});
System.out.println(maxSUm); // prints 7
}
static int maxSumSubArray(int [] a){
int size = a.length;
int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
for (int i = 0; i < size; i )
{
max_ending_here = max_ending_here a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
}
uj5u.com熱心網友回復：
根據wiki，正確答案是 7 所以代碼是正確的。
為什么？因為子陣列還包括陣列的最小和最大邊界：
A[0..n] -> 找到邊界為 i,j 的子陣列，其中 0<=i<=j<=n; 在你的情況下 i=0 和 j=6 （整個陣列）
uj5u.com熱心網友回復：
代碼沒有任何問題，正確答案是將所有數字相加得到 7。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/325482.html
標籤：爪哇 数组 算法 kadanes-算法
上一篇：確定a、b中是否存在數字n1、n2和c中的n3，使得n1 n2=n3[ftt，多項式乘法]
下一篇：查找完整二叉樹的不相關磁區