【Python】長さ3の増加部分列(トリプレット)を判定するアルゴリズムを解説

ソートされていない整数型の配列が与えられたとき、その中に「長さ3の増加部分列」が存在するかどうかを判定する問題を考えます。本記事では、Pythonを使ってこの問題を線形時間で解く効率的なアルゴリズムを紹介します。

問題の定義

正式には、この関数は以下の条件を満たす必要があります。

• インデックス i、j、k が存在し、0 ≤ i < j < k ≤ n-1 の条件下で arr[i] < arr[j] < arr[k] を満たす場合は true を返す
• そのような組み合わせが存在しない場合は false を返す

解法のアプローチ

この問題は、2つの変数 small と big を使う貪欲法(グリーディー法)により、時間計算量 O(n)、空間計算量 O(1) で解くことができます。手順は以下の通りです。

• small := 無限大、big := 無限大 として初期化する
• 配列の各要素 i について以下を繰り返す
  • i <= small の場合:small := i と更新する
  • それ以外で i <= big の場合:big := i と更新する
  • どちらにも当てはまらない場合:i は small よりも大きく、big よりも後に出現した値であるため、増加トリプレットの存在が確定し、true を返す
• ループが終了しても true が返らなければ、false を返す

実装例

class Solution(object):
   def increasingTriplet(self, nums):
      small,big = 100000000000000000000,100000000000000000000
      for i in nums:
         if i <= small:
            small = i
         elif i<=big:
            big = i
         else :
            return True
      return False
ob1 = Solution()
print(ob1.increasingTriplet([5,3,8,2,7,9,4]))

入力

[5,3,8,2,7,9,4]

出力

True

アルゴリズムのポイント

このアルゴリズムの鍵となるのは、small と big の更新ロジックです。small には「これまでに見つかった最小値」、big には「small 以降に現れた、small より大きい値のうち最小のもの」が保持されます。したがって、ある要素が big よりも大きければ、必ず「small < big < その要素」という増加関係が成立していることになります。

なお、実務のコードでは巨大な定数の代わりに float('inf') を使うと、より安全で可読性の高い実装になります。