C++で最長増加部分列の個数を求める方法

問題概要

ソートされていない整数の配列が与えられたとき、「最長増加部分列(LIS: Longest Increasing Subsequence)」の個数を求める問題を考えます。

例えば、入力が [1, 3, 5, 4, 7] の場合を考えてみましょう。このとき最長増加部分列は [1, 3, 5, 7] と [1, 3, 4, 7] の2通りが存在するため、出力は 2 となります。

解法のアプローチ

この問題は動的計画法(DP)を用いて効率的に解くことができます。ポイントは、各インデックスについて「その要素を末尾とする最長増加部分列の長さ」と「その長さとなる部分列の個数」の2つを同時に管理することです。

具体的には、以下の手順で解きます。

1. 配列のサイズを n とし、長さ n の2つの配列 len と cnt を用意して、すべて 1 で初期化します。len[i] は「i番目の要素で終わる増加部分列の最長の長さ」、cnt[i] は「その長さを持つ部分列の個数」を表します。
2. 変数 lis を 1 で初期化します(全体の最長増加部分列の長さ)。
3. i を 1 から n-1 まで順に処理します。
   • j を 0 から i-1 まで順に処理します。
   • nums[i] > nums[j] を満たす場合:
     • len[j] + 1 > len[i] ならば、len[i] := len[j] + 1 とし、cnt[i] := cnt[j] と更新します(より長い部分列が見つかったため、個数を引き継ぎます)。
     • そうでなく len[j] + 1 == len[i] を満たす場合は、cnt[i] := cnt[i] + cnt[j] とします(同じ長さの部分列が新たに見つかったため、個数を加算します)。
   • lis を lis と len[i] の最大値で更新します。
4. 答え ans を 0 で初期化します。
5. i を 0 から n-1 まで走査し、len[i] == lis となるすべての i について、ans に cnt[i] を加算します。
6. ans を返します。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findNumberOfLIS(vector<int>& nums) {
      int n = nums.size();
      vector <int> len(n, 1), cnt(n, 1);
      int lis = 1;
      for(int i = 1; i < n; i++){
         for(int j = 0; j < i; j++){
            if(nums[i] > nums[j]){
               if(len[j] + 1 > len[i]){
                  len[i] = len[j] + 1;
                  cnt[i] = cnt[j];
               }
               else if(len[j] + 1 == len[i]){
                  cnt[i] += cnt[j];
               }
            }
            lis = max(lis, len[i]);
         }
      }
      int ans = 0;
      for(int i = 0; i < n; i++){
         if(len[i] == lis)ans += cnt[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,5,4,7};
   cout << (ob.findNumberOfLIS(v));
}

入力

[1,3,5,4,7]

出力

2

計算量の評価

このアルゴリズムの時間計算量は、要素のペアを二重ループで調べるため O(n²) です。また、補助配列として len と cnt の2つを使用するため、空間計算量は O(n) となります。

このように、動的計画法を活用することで、最長増加部分列の「長さ」だけでなく「個数」も同時に求めることができます。類似の問題として、単純に最長増加部分列の長さを求める LIS 問題がありますので、あわせて学習すると理解が深まります。