C++でソート済み配列を作るための最大チャンク数を求める方法（Max Chunks To Make Sorted II）

整数の配列 arr が与えられたとき、この配列をいくつかの区間（パーティション）に分割し、それぞれの区間を個別にソートします。その後、各区間を連結すると、全体として1つのソート済み配列が得られます。このとき、作成できるパーティションの最大数はいくつになるでしょうか？

例えば、入力が [3,2,4,5,5] の場合、出力は 4 になります。これは、[3,2]、[4]、[5]、[5] のように4つの区間に分割でき、それぞれをソートして連結すると [2,3,4,5,5] というソート済み配列が得られるからです。

解法のアプローチ

この問題は「左側からの最大値」と「右側からの最小値」を比較するというシンプルな発想で解くことができます。ある位置で区切りを入れられる条件は、「左側部分の最大値が右側部分の最小値以下である」ことです。この条件を満たす位置ごとに区切りを入れることで、最大のチャンク数を求められます。

アルゴリズムの手順

• カウンタ cnt を 1 で初期化します（配列全体が1つのチャンクになるため）。
• 配列のサイズを n とします。
• サイズ n の配列 maxOfLeft を定義します。maxOfLeft[i] はインデックス 0 から i までの最大値を格納します。
• サイズ n の配列 minOfRight を定義します。minOfRight[i] はインデックス i から n-1 までの最小値を格納します。
• maxOfLeft[0] = arr[0] とし、インデックス 1 から順に maxOfLeft[i] = max(maxOfLeft[i-1], arr[i]) を計算します。
• minOfRight[n-1] = arr[n-1] とし、インデックス n-2 から逆順に minOfRight[i] = min(minOfRight[i+1], arr[i]) を計算します。
• インデックス 0 から n-2 まで走査し、minOfRight[i+1] >= maxOfLeft[i] が成り立つたびに cnt を増やします。これは、位置 i の直後で区切れることを意味します。
• 最後に cnt を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxChunksToSorted(vector<int>& arr) {
      int cnt = 1;
      int n = arr.size();
      vector<int> maxOfLeft(n);
      vector<int> minOfRight(n);
      maxOfLeft[0] = arr[0];
      for (int i = 1; i < n; i++)
         maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
         minOfRight[n - 1] = arr[n - 1];
      for (int i = n - 2; i >= 0; i--)
         minOfRight[i] = min(minOfRight[i + 1], arr[i]);
      for (int i = 0; i < n - 1; i++) {
         if (minOfRight[i + 1] >= maxOfLeft[i])
         cnt++;
      }
      return cnt;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,5,5};
   cout << (ob.maxChunksToSorted(v));
}

入力

{3,2,4,5,5}

出力

4

計算量について

このアルゴリズムは、前処理として左右からの累積最大値・最小値の計算に O(n)、最後の走査にも O(n) かかるため、全体の時間計算量は O(n) です。また、補助配列を2つ使用するため、空間計算量も O(n) となります。ソートを行わずに線形時間で解けるのがこの手法の大きな利点です。