9

JavaでKadaneのアルゴリズムを次のように実装しています。基本的には、連続する部分配列の最大合計を見つけることです。

String[] numbers = string.split(",");
                int max_so_far = 0;
                int max_ending_here = 0;
                for (int i = 0; i < numbers.length-1;i++){
                     max_ending_here = max_ending_here + Integer.parseInt(numbers[i]);
                     if (max_ending_here < 0)
                         max_ending_here = 0;
                     if (max_so_far < max_ending_here)
                          max_so_far = max_ending_here;
                }
                System.out.println(max_so_far);

ただし、配列に負の数と正の数の組み合わせがある場合、これは機能しません。たとえば、次のようになります。

2,3,-2,-1,10

最大値として 12 を返す必要があります。今のところ5を返します

4

4 に答える 4

12

アルゴリズムの実装は問題ないように見えますが、ループ条件i < numbers.length-1はそうではありません。配列の終わりのわずか1手前で停止します。i < numbers.lengthやるべきです:-)

于 2011-08-29T16:43:21.840 に答える
4

これは私のために働く：

    String string = "2,3,-2,-1,10";
    String[] numbers = string.split(",");
    int max_so_far = 0;
    int max_ending_here = 0;
    for (String num : numbers) {
        int x = Integer.parseInt(num);
        max_ending_here = Math.max(0, max_ending_here + x);
        max_so_far = Math.max(max_so_far, max_ending_here);
    }
    System.out.println(max_so_far);
于 2011-08-29T16:53:29.630 に答える
2

Michał Šrajerによる上記の回答について:

行 #7: max_ending_here = Math.max(0, max_ending_here + x);

次のようにする必要があります。

max_ending_here = Math.max(x, max_ending_here + x);

...ここで定義されている Kadane アルゴリズムによると

于 2012-09-06T03:14:37.033 に答える