C++で最長連続増加部分列（LCIS）の長さを求める方法

問題の概要

整数の配列が与えられたとき、最長連続増加部分配列（Longest Continuous Increasing Subsequence）の長さを求める問題を考えてみましょう。「連続増加」とは、隣り合う要素が単調に増加し続けている状態を指します。

例えば、入力が [2,4,6,5,8] の場合、出力は 3 になります。最も長い連続増加部分列は [2,4,6] であり、その長さが 3 であるためです。

アルゴリズムの考え方

この問題は、配列を一度だけ走査すれば解決できます。具体的な手順は次の通りです。

• 配列 nums のサイズが 1 以下の場合は、そのサイズをそのまま返します。
• answer を 1、count を 1 に初期化します。answer は現時点での最大長、count は現在の連続増加の長さを記録する変数です。
• i を 0 から配列の末尾の手前まで順にループさせます。
  • nums[i] < nums[i + 1] の場合：増加が続いているので count を 1 増やし、answer を max(answer, count) で更新します。
  • それ以外の場合：増加が途切れたため、count を 1 にリセットします。
• 最後に answer を返します。

C++による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findLengthOfLCIS(vector<int>& nums) {
      if (nums.size() <= 1)
         return nums.size();
      int answer = 1, count = 1;
      for (int i = 0; i < nums.size() - 1; i++) {
         if (nums[i] < nums[i + 1]) {
            count++;
            answer = max(answer, count);
         }
         else {
            count = 1;
         }
      }
      return answer;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,4,6,5,8};
   cout << (ob.findLengthOfLCIS(v));
}

実行結果

入力：

{2,4,6,5,8}

出力：

3

計算量について

このアルゴリズムの計算量は以下の通りです。

• 時間計算量：O(n) — 配列を一度だけ走査するため、要素数 n に対して線形時間で処理できます。
• 空間計算量：O(1) — 追加で使用するのは変数 2 つのみであり、メモリ効率が非常に良いのが特徴です。

このように、シンプルなカウンタ管理だけで最長連続増加部分列の長さを効率的に求められます。類似の「最長増加部分列（LIS）」の問題とは異なり、連続性が求められる分、動的計画法を使わずとも容易に解ける点がポイントです。