Pythonで配列をソート済みにできる最大チャンク数を見つけるプログラム

問題の概要

配列 nums が与えられたとき、この配列をいくつかの区間（パーティション／チャンク）に分割し、それぞれを個別にソートします。その後、すべてを連結した結果が完全にソート済みの配列になるとします。このとき、作成できるパーティションの最大数を求めるのが本記事のテーマです。

例えば、入力が [3,2,4,5,5] の場合、出力は 4 になります。[3,2]、[4][5]、[5] のように4つのパーティションに分割でき、それぞれをソートして連結すると [2,3,4,5,5] という完全に整列した配列が得られるからです。

解法のアプローチ

この問題は「貪欲法」で解くことができます。ある区間が独立したチャンクとして成立する条件は、その区間だけをソートした結果が、完全にソートした配列の同じ位置の要素と一致することです。左端から順に、できるだけ小さい区間から試していき、一致しなければ区間を1つずつ広げて再チェックします。

具体的な手順は以下の通りです。

• まず、元の配列 nums をソートした配列 real を用意します。これが最終的な目標の配列です。
• ポインタ p1 := 0、p2 := 1、カウンタ c := 0 を初期化します。
• 以下の処理を繰り返します。
  • flag := True とします。
  • nums[p1:p2] の部分配列をソートしたものを tmp とします。
  • j を 0 から tmp のサイズまで動かし、tmp[j] と real[p1+j] を比較します。
  • 一致しない要素が見つかった場合は flag := False とし、p2 を 1 増やして（区間を広げて）内側のループを抜けます。
  • flag が True のままなら、この区間は独立したチャンクとして成立しているので、p1 := p2、p2 := p2 + 1 と更新し、カウンタ c を 1 増やします。
  • p1 が配列の長さと等しい、または p2 が配列の長さを超えた時点で、c を返して終了します。

実装例

以下は上記のアルゴリズムを Python で実装したコードです。

def solve(nums):
    real = sorted(nums)
    p1, p2, c = 0, 1, 0
    while True:
        flag = True
        tmp = sorted(nums[p1:p2])
        for j in range(len(tmp)):
            if tmp[j] != real[p1 + j]:
                flag = False
                p2 += 1
                break
        if flag:
            p1, p2 = p2, p2 + 1
            c += 1
        if p1 == len(nums) or p2 > len(nums):
            return c

nums = [3, 2, 4, 5, 5]
print(solve(nums))

入力

{3,2,4,5,5}

出力

4

計算量について

この実装では、区間が確定するたびに部分配列のソートと比較を行うため、最悪の場合の時間計算量は O(n² log n) 程度になります。より効率的な実装としては、「現在位置までの最大値」と「ソート済み配列の同位置の値」を比較する方法や、接頭辞の最大値を使った O(n) の解法も知られています。ただし、本記事の手法はロジックが直感的で理解しやすいため、学習用途には非常に適しています。