定義

LIS（最長増加部分列）は、配列から順序を維持しながら増加する最長の部分列を見つけるアルゴリズムです。連続でなくても良く、元の順序だけ維持すれば良いです。

主な特性

• ✓dp[i] = arr[i]で終わるLISの長さ
• ✓時間計算量: O(n²) (二分探索使用時 O(n log n))
• ✓prev配列で逆追跡して実際のLISを復元
• ✓全てのdp[i]は最小1（自分自身）

時間計算量