0

以下はコード スニペットです。部分配列の最大合計は 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;
    }
}
4

2 に答える 2

2

wikiによると正解は7なのでコードは正しいです。

なんで？subarray には配列の最小境界と最大境界も含まれているため、次のようになります。

A[0..n] -> 0<=i<=j<=n; の境界 i,j を持つ部分配列を検索します。そしてあなたの場合、i = 0およびj = 6（配列全体）

于 2021-10-16T17:56:10.553 に答える