Pythonで線形時間O(n)にサイズ3の増加部分列を見つける方法

問題の概要

N個の数値を含む配列が与えられたとき、b[i] < b[j] < b[k] かつ i < j < k を満たす3つの要素が存在するかどうかを、線形時間（O(n)）で判定する方法を解説します。該当する組み合わせが複数ある場合は、そのうちのどれか1つを出力すれば構いません。

例えば、入力が [13, 12, 11, 6, 7, 3, 31] の場合、出力は [6, 7, 31] となります。

解決のためのアプローチ

この問題は、「各要素の左側にもっと小さい値が存在するか」「各要素の右側にもっと大きい値が存在するか」を事前に計算しておくことで効率的に解けます。具体的には、次の手順に従います。

• n := 配列Aのサイズ
• maximum := n-1、minimum := 0
• smaller := サイズ1000の配列を0で初期化し、smaller[0] := -1 とする
• i を1からn-1まで繰り返す：
  　・A[i] <= A[minimum] の場合 → minimum := i、smaller[i] := -1
  　・それ以外の場合 → smaller[i] := minimum
• greater := サイズ1000の配列を0で初期化し、greater[n-1] := -1 とする
• i をn-2から0まで逆順に繰り返す：
  　・A[i] >= A[maximum] の場合 → maximum := i、greater[i] := -1
  　・それ以外の場合 → greater[i] := maximum
• i を0からn-1まで繰り返し、smaller[i] != -1 かつ greater[i] != -1 となるiが見つかれば、A[smaller[i]]、A[i]、A[greater[i]] を返す
• 見つからなければ "Nothing" を返す

アルゴリズムのポイント

smaller配列には「各インデックスiより左側にある最小値のインデックス」を記録し、greater配列には「各インデックスiより右側にある最大値のインデックス」を記録します。-1は「条件を満たす要素が存在しない」ことを表します。

最終的に、smallerとgreaterの両方が有効な値を持つインデックスiが見つかれば、その位置が中央の要素となり、増加する3つの要素の組が確定します。処理は合計3回の走査で構成され、それぞれO(n)であるため、計算量はO(n)、追加メモリもO(n)で抑えられます。

実装例

以下のPythonコードで実際の動作を確認できます。

def find_inc_seq(A):
    n = len(A)
    maximum = n-1
    minimum = 0
    smaller = [0]*10000
    smaller[0] = -1
    for i in range(1, n):
        if (A[i] <= A[minimum]):
            minimum = i
            smaller[i] = -1
        else:
            smaller[i] = minimum
    greater = [0]*10000
    greater[n-1] = -1
    for i in range(n-2, -1, -1):
        if (A[i] >= A[maximum]):
            maximum = i
            greater[i] = -1
        else:
            greater[i] = maximum
    for i in range(0, n):
        if smaller[i] != -1 and greater[i] != -1:
            return A[smaller[i]], A[i], A[greater[i]]
    return "Nothing"

arr = [13, 12, 11, 6, 7, 3, 31]
print(find_inc_seq(arr))

入力

[13, 12, 11, 6, 7, 3, 31]

出力

(6, 7, 31)