Pythonでリスト全体がソートされるように分割できるサブリストの最大数を求めるアルゴリズム

問題の概要

数値のリスト nums が与えられたとします。このリストは複数の部分リスト(サブリスト)に分割でき、それぞれの部分を個別にソートすることが可能です。ここで求めたいのは、分割・ソートを行った後にリスト全体がソート済みの状態になるような、部分リスト数の最大値です。

例えば、入力が nums = [4, 3, 2, 1, 7, 5] の場合、答えは 2 になります。[4, 3, 2, 1] と [7, 5] の2つの部分リストに分割し、それぞれをソートすれば [1, 2, 3, 4, 5, 7] という完全にソートされたリストが得られるためです。

解法の考え方:累積和による分割境界の検出

この問題は「累積和」を使うことでシンプルに解けます。元のリストとソート済みリストを先頭から同時に走査し、ある位置までの累積和が一致した時点で、そこを有効な分割境界と判断します。

なぜこれで正しく判定できるのでしょうか。ある位置で累積和が一致するということは、その位置までの要素の集合が元のリストとソート済みリストで同一であることを意味します。つまり、その境界より前の部分だけを独立にソートしても、後続の要素との相対的な順序には影響せず、結果として全体が正しくソートされるのです。

アルゴリズムの手順

• count を 0 で初期化する
• main_sum(元のリストの累積和)と sorted_sum(ソート済みリストの累積和)を 0 で初期化する
• nums の各要素 x と、ソート済みリストの対応する要素 y に対して以下を繰り返す:
  • main_sum に x を加算する
  • sorted_sum に y を加算する
  • 両者の値が等しければ count を 1 増やす(分割境界を発見)
• 最終的な count を返す

実装例(Python)

class Solution:
    def solve(self, nums):
        count = 0
        main_sum = sorted_sum = 0

        for x, y in zip(nums, sorted(nums)):
            main_sum += x
            sorted_sum += y
            if main_sum == sorted_sum:
                count += 1

        return count

ob = Solution()
nums = [4, 3, 2, 1, 7, 5]
print(ob.solve(nums))

入力

[4, 3, 2, 1, 7, 5]

出力

2

計算量の評価

このアルゴリズムの時間計算量は O(n log n) です。ボトルネックは最初のソート処理であり、その後の走査は単一のループで完結します。空間計算量はソート済みリストのコピーが必要なため O(n) となります。累積和の一致という直感的な指標だけで境界を検出できる点が、この解法の美しさと言えるでしょう。