3

Kadane のアルゴリズム ( http://en.wikipedia.org/wiki/Maximum_subarray_problem ) を使用して、数値の 1 次元配列内の連続する部分配列の最大合計を見つけます。

では、これをどのように使用して、同じ最大和を持つシーケンスの数を見つけるのでしょうか? そのようなシーケンスをカウントするためにアルゴリズムにどのような変更を加えることができますか..

例： 

0 0 0 1     -> (largest sum = 1); 4 sequences  { (0,0,0,1), (0,0,1), (0,1) , (1) }

0 0 0       -> (largest sum = 0); 6 sequences { (0,0,0), (0,0), (0,0), (0), (0), (0) }

2 0 -2 2    -> (largest sum = 2); 4 sequences { (2), (2,0), (2,0,-2, 2), (2) }
4

1 に答える 1

2

Kadane のアルゴリズムは、現在のポイントで終了するシーケンスの最大値と、これまでに確認された最大値を追跡します。

ウィキペディアのページに基づく Python 実装を次に示します。

def kadane(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max([x,0,max_ending_here+x])
        max_so_far = max(max_so_far,max_ending_here)
    return max_so_far

2 つの変数を追加することで、このようなシーケンスの数を追跡するようにアルゴリズムを変更できます。

  • count_with_max_ending_hereは、合計が max_ending_here になる値で、現在のポイントで終了するシーケンスの数をカウントします
  • count_with_maxは、これまでに見つかったシーケンスの数を最大値でカウントします

Kadane のアルゴリズムは、O(n) の複雑さを維持しながら、これらの変数を追跡するように簡単に変更できます。

def kadane_count(A):
    max_ending_here = max_so_far = 0
    count_with_max_ending_here = 0 # Number of nontrivial sequences that sum to max_ending_here
    count_with_max = 0
    for i,x in enumerate(A):
        new_max = max_ending_here+x
        if new_max>=0:
            if count_with_max_ending_here==0:
                # Start a nontrivial sequence here
                count_with_max_ending_here=1
            elif max_ending_here==0:
                # Can choose to carry on a nontrivial sequence, or start a new one here
                count_with_max_ending_here += 1
            max_ending_here = new_max
        else:
            count_with_max_ending_here = 0 
            max_ending_here = 0

        if max_ending_here > max_so_far:
            count_with_max = count_with_max_ending_here
            max_so_far = max_ending_here
        elif max_ending_here == max_so_far:
            count_with_max += count_with_max_ending_here

    return count_with_max

for A in [ [0,0,0,1],[0,0,0],[2,0,-2,2] ]:
    print kadane(A),kadane_count(A)
于 2013-06-10T18:19:29.167 に答える