問題
整数のnums をnums から
- 長さを
返せば よく、 列その ものは 返しません numsの長さは 1 以上 2500 以下、 値は どれも 絶対値が 10000 以下です - 書き終えたら、
O(n²) より 速い 書き方も 示してください
入力と出力の例
例 1
1、
入力
nums = [3, 1, 8, 2, 5, 9, 4]出力
4例 2
等しい
入力
nums = [5, 5, 5]出力
1例 3
2、
入力
nums = [2, 6, 8, 3, 4, 5, 1]出力
4面接での聞かれ方
面接では、
- 「配列の
最長増加部 分列の 長さを 返してください」 - O(n²) の DP を
書き終えると、 「n が 10 万なら？」 「O(n log n) に できますか」と 聞かれます。 シニアの 面接では、 ここからが本番です - 「速い
書き方の 途中の 配列は、 答えの 列その ものですか」と、 仕組みを 分かっているかを 確かめられます - 「長さではなく
列その ものを 返すには？」と 続く こともあります
「部分列」は
アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。
まず
段 1
まずend[i] をnums[i] でnums[i] のi よりnums[i] よりnums[j] です。end[i] は、j の end[j] のend の
Python で
Python
def lis_slow(nums):
end = [1] * len(nums)
for i, x in enumerate(nums):
for j in range(i):
if nums[j] >= x:
continue
c = end[j] + 1
if c > end[i]:
end[i] = c
return max(end)段 2
速くtail[L - 1] にtail は
段 3
数 x をtail のx 以上のx でx をtail のx よりx 以上」を
解答
Python
Python
from bisect import bisect_left
def lis_length(nums):
tail = []
for x in nums:
i = bisect_left(tail, x)
if i == len(tail):
tail.append(x)
else:
tail[i] = x
return len(tail)JavaScript
JavaScript
function lisLength(nums) {
const tail = [];
for (const x of nums) {
let lo = 0;
let hi = tail.length;
while (lo < hi) {
const m = (lo + hi) >> 1;
if (tail[m] < x) {
lo = m + 1;
} else {
hi = m;
}
}
tail[lo] = x;
}
return tail.length;
}Go
Go
import "sort"
func lisLength(
nums []int,
) int {
tail := []int{}
for _, x := range nums {
i := sort.SearchInts(
tail, x,
)
if i == len(tail) {
tail = append(tail, x)
} else {
tail[i] = x
}
}
return len(tail)
}JavaScript の tail[lo] = x は、lo がbisect_left と Go の sort.SearchInts は、x 以上の
計算量
- 時間は O(n log n) です。
数を 1 つ 見る たびに、 長さ n 以下の tailを二分探索するので、 1 回あたり O(log n) です - 使う
記憶は O(n) です。 tailは最悪で 全部の 数を 持ちます (並びが はじめから 増えているとき) - O(n²) の DP は、
時間 O(n²)、 記憶 O(n) です。 n が 2500 なら 300 万回ほどで 間に 合いますが、 n が 10 万なら 50 億回に なり、 速い 書き方が要ります
よく
tailを答えの 列だと思う。 例 3 で 最後まで 見ると、 tailは[1, 3, 4, 5]になります。 1 は 5 より 後ろに あるので、 これは 並びの 中の 増える 列では ありません。 長さだけが 正しく、 中身は 「長さごとの 最も 小さい 末尾」の 記録です。 列その ものが 要るなら、 各数が どの 位置に 入ったかと 前の 数への 印を 別に持ちます xより大きい 最初の 位置を探す。 Python で bisect_rightを使うと、 例 2 の [5, 5, 5]で 5 が 3 回足され、3 を 返します。 狭義に 増える 列では bisect_leftです (広義に増える 列なら bisect_rightが正しくなります) - DP の
答えを 最後の 要素にする。 O(n²) の DP で end[n - 1]を返すと、 例 3 では 1 で 終わる 列の 長さ 1 を 返します。 答えは endの最大です - 部分配列と
取り違える。 続いた 区間で 増える 最長を 求める 書き方 (前と 比べて 伸ばすか 切るか ) を 書くと、 例 1 で 3、 8 が 切れて 2 などに なります。 飛び 飛びに 選べる ことを 確かめてから書きます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「まず、
各位置で 終わる 増える 列の 最長を、 それより 前の 小さい 数の 答えから 作る DP で 書けます。 これは O(n²) です。 速く するには、 長さごとに 『その 長さの 増える 列の 最も 小さい 末尾』を 覚える 配列を 持ちます。 この 配列は 小さい 順に 並ぶので、 数を 1 つ 見る たびに 二分探索で、 その 数以上の 最初の 位置を 置き換えるか、 無ければ 末尾に 足します。 最後の 配列の 長さが 答えで、 時間は O(n log n)、 記憶は O(n) です。」
書き終えたら、
「例 3 の
[2, 6, 8, 3, 4, 5, 1]でたどります。 2、 6、 8 は 足していき [2, 6, 8]です。3 は 6 の 位置を 置き換えて [2, 3, 8]、4 は 8 を 置き換えて [2, 3, 4]、5 は 足して [2, 3, 4, 5]です。最後の 1 は 2 を 置き換えて [1, 3, 4, 5]になりますが、 長さは 4 のままです。 答えは 4 で、 この 配列 その ものは 並びの 中の 列ではない 点に 気を つけます。」