最長増加部分列 (LeetCode 300)

整数配列が与えられた場合、その中に含まれる最長の狭義増加部分列（Strictly Increasing Subsequence）の長さを見つけます。部分列とは、配列から要素をいくつか（0個でもよい）削除し、残りの要素の順序を変更しないで得られる配列のことを指します。

この問題は動的計画法（DP）を用いて解くのが一般的です。2層のループ構造が必要となり、ポイントとなるのはDP配列（状態テーブル）の定義と状態遷移のロジックです。

アルゴリズムのアプローチ：

1. DP配列の定義：
   memo[i]を、インデックスiの要素で終わる最長の増加部分列の長さと定義します。この定義により、i以前の要素jとの大小関係を比較する際に、それぞれの終点で正当な部分列を扱うことができます。
2. 状態遷移式：
   インデックスiにおける最長増加部分列の長さは、それ以前のすべてのインデックスj（0 <= j < i）に対して、nums[i] > nums[j]であるかどうかを確認し、条件を満たす場合にmemo[j] + 1の最大値をとることで決定します。
   式：if (nums[i] > nums[j]) memo[i] = max(memo[i], memo[j] + 1);
3. 初期化：
   どの位置でも少なくともその要素自身だけの部分列（長さ1）は存在するため、すべてのmemo[i]は初期値1とします。
4. 計算順序：
   memo[i]はそれ以前のmemo[j]に依存するため、前から後ろへ向かってループを回します。

以下にC++による実装例を示します。変数名や構造を変更してあります。

class Solution {
public:
    int lengthOfLIS(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1) return n;
        
        vector<int> memo(n, 1);
        int maxLen = 0;
        
        for (int i = 1; i < n; ++i) {
            for (int prev = 0; prev < i; ++prev) {
                if (arr[i] > arr[prev]) {
                    memo[i] = max(memo[i], memo[prev] + 1);
                }
            }
            maxLen = max(maxLen, memo[i]);
        }
        return maxLen;
    }
};

• 時間計算量: O(n²)
• 空間計算量: O(n)

最長連続増加部分列 (LeetCode 674)

ソートされていない整数配列が与えられた場合、最長かつ連続的に増加する部分列（連続増加部分列）の長さを返します。連続増加部分列は、隣り合う要素が厳密に増加している部分です。

この問題は前の問題よりも単純です。要素が隣接している必要があるため、直前の要素との比較のみで状態を更新できます。

動的計画法による実装：
dp[i]をインデックスiで終わる最長連続増加部分列の長さとします。nums[i]がnums[i-1]より大きい場合はdp[i] = dp[i-1] + 1となり、それ以外の場合は1（初期値）に戻ります。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& arr) {
        if (arr.empty()) return 0;
        
        int n = arr.size();
        vector<int> dp(n, 1);
        int result = 1;
        
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};

• 時間計算量: O(n)
• 空間計算量: O(n) ※変数を1つだけ使ってO(1)に最適化することも可能です。

最長重複部分配列 (LeetCode 718)

2つの整数配列nums1とnums2が与えられたとき、両方の配列に共通して含まれる最長の部分配列（連続する部分列）の長さを返します。

この問題は典型的な2次元動的計画法の問題です。2つの配列の要素をすべて比較する必要があるため、2次元のDPテーブルを使用します。

DPテーブルの設計コツ：
境界条件の処理を簡略化するために、DPテーブルの定義に少し工夫を加えます。

1. DP配列の定義：
   dp[i][j]を、nums1のi-1番目までの要素と、nums2のj-1番目までの要素において、最後尾が一致する最長の部分配列の長さと定義します。この定義により、配列のインデックスとDPテーブルのインデックスに1つずらし（offset）が生じ、初期化が容易になります。
2. 状態遷移式：
   nums1[i-1]とnums2[j-1]が等しい場合、その位置より前の最長共通部分配列の長さに1を足したものが現在の長さとなります。
   式：if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
3. 初期化：
   上記の定義（i-1, j-1までを見る）により、dp[0][j]およびdp[i][0]は「空の配列との一致」を意味するため、すべて0で初期化されます。これにより、i=1, j=1から始まる計算で最初の一致を正しく数え上げることができます（0 + 1 = 1）。
4. 計算順序：
   2重ループを用いてnums1とnums2の各要素を順に走査します。

以下にC++による実装例を示します。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        // dp[i][j] は Aのi-1文字目とBのj-1文字目までの共通接尾辞の長さ
        vector dp(m + 1, vector<int>(n + 1, 0));
        int maxLen = 0;
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen;
    }
};

• 時間計算量: O(m × n)
• 空間計算量: O(m × n) ※空間最適化によりO(min(m, n))に削減可能です。