arrays - フェンウィック ツリーまたは BIT を使用した配列内の非減少サブシーケンスの最大合計

Question

フェンウィック木を使用して、配列内の非減少サブシーケンスの最大和を見つけるにはどうすればよいですか? たとえば、1 4 4 2 2 3 3 1 がある場合、非減少サブシーケンスの最大合計は 11 (1 2 2 3 3) です。

Answer 1

最大合計は、動的計画法アルゴリズムを使用して見つけることができます。配列をスキャンし、各要素の値を、有効な最大のサブシーケンス合計に追加します (サブシーケンスは、この要素以下の値で終了します)。

効率的な実装には、特定のサブ範囲で最大値をすばやく見つける何らかの方法が必要です。拡張二分探索木を使用してそれを行うことができます。フェンウィック木は、拡張二分探索木の効率的な実装です。フェンウィック ツリーの最も一般的な用途は、あるサブ範囲内の値の合計を見つけることです。些細な変更により、それを使用してサブ範囲の最大値を見つけることができます (この特定のケースでは、フェンウィック ツリーの値が決して減少しないため、これが機能します)。

詳細については、次の Python コードを参照してください。

array = [1, 4, 4, 2, 2, 3, 3, 1]

numbers = sorted(set(array))
n = len(numbers)
indexes = {numbers[v]:v+1 for v in range(0, n)}
n += 1
bit = [0] * n
result = 0

for x in array:
    pos = indexes[x]
    i = pos
    maximum = 0
    while i != 0:
        maximum = max(maximum, bit[i])
        i = i & (i-1)
    x += maximum
    i = pos
    while i < n:
        bit[i] = max(bit[i], x)
        i += i & -i
    result = max(result, x)

print(result)

indexesディクショナリは、フェンウィック ツリーのサイズを入力配列の最大数から配列のサイズに縮小するために使用されます。最初の入れ子whileは、フェンウィック ツリーのサブ範囲の最大値を検出します。合計の 1 つが更新された後、 2 番目にネストされたwhileFenwick ツリーが更新されます。

このコードは、正数の配列に対してのみ機能します。一般に、入力配列は、正でない数値をすべて除外することによって前処理する必要があります。

時間計算量は O(N log N) です。スペースの複雑さは O(N) です。