C#で数値配列の最長連続増加部分列の長さを求める方法

C#で最長連続増加部分列の長さを求めるアルゴリズム

longestIncreasingSubsequenceメソッドは、配列内で隣り合う要素が連続して増加している区間（部分列）の中から、最も長いものの長さを整数として返します。仕組みはシンプルで、forループで配列を先頭から順に走査しながら、現在の増加列の長さを変数countで追跡し、その都度最大値resを更新していきます。

計算量

• 時間計算量：O(N) ― 配列の各要素を一度だけ訪問するため
• 空間計算量：O(1) ― カウンタ用の変数以外に追加の記憶領域を必要としないため

例

入力：{2, 4, 6, 5, 8}
出力：3

この配列では「2 → 4 → 6」が長さ3の連続増加部分列となり、これが最長です（後半は「5 → 8」の長さ2にとどまります）。

実装例

using System;

public class Arrays {
    public int longestIncreasingSubsequence(int[] nums) {
        // 配列がnullまたは空の場合は-1を返す
        if (nums == null || nums.Length == 0) {
            return -1;
        }

        int res = 0;   // 最長の連続増加部分列の長さ
        int count = 0; // 現在の連続増加部分列の長さ

        for (int i = 0; i < nums.Length; i++) {
            if (i == 0 || nums[i] > nums[i - 1]) {
                // 増加が続いている場合
                count++;
                res = Math.Max(res, count);
            } else {
                // 増加が途切れた場合はカウントをリセット
                count = 1;
            }
        }
        return res;
    }
}

class Program {
    static void Main(string[] args) {
        var arrays = new Arrays();
        int[] nums = { 1, 3, 5, 4, 7 };
        Console.WriteLine(arrays.longestIncreasingSubsequence(nums));
    }
}

出力

3

コードのポイント

1. 初期チェック：配列がnullまたは空の場合は、有効な結果が得られないため-1を返します。
2. 2つのカウンタ：resは全体での最長記録、countは現在走査中の連続増加列の長さを保持します。
3. 増加の判定：先頭要素（i == 0）、または現在の要素が直前の要素より大きい場合（nums[i] > nums[i - 1]）はcountを+1し、resを更新します。
4. リセット処理：増加が途切れた時点でcountを1に戻し、新しい増加列のカウントを開始します。

動作の流れ（入力：{1, 3, 5, 4, 7}）

最終的にresには、最長の連続増加部分列「1 → 3 → 5」の長さである3が格納されます。