31. Longest Increasing Subsequence

読了目安約2分

DP / LeetCode 300 (Medium) — 最長増加部分列の長さを O(N²) の DP で求める。

この章の目次

問題

LeetCode 300. Longest Increasing Subsequence（Medium / カテゴリ: DP）

整数の配列 nums が与えられます。配列から要素をいくつか選び、元の順序を保って並べたものを部分列と呼びます。後ろの要素ほど真に大きくなる部分列（増加部分列）の、最大の長さを返してください。配列の長さは 1 以上 2500 以下です。

考え方

ヒント 1

状態を dp[i] = 「nums[i] で終わる増加部分列の最長の長さ」と定めます。答えは dp 全体の最大値です。

ヒント 2

初期条件はすべて dp[i] = 1（自分 1 個だけの列）です。 j < i かつ nums[j] < nums[i] なら、nums[j] で終わる列の後ろに nums[i] をつなげられます。遷移は dp[i] = max(dp[i], dp[j] + 1) で、すべての j を試します。

「長さ k の増加部分列の末尾の最小値」を並べた配列を二分探索で更新すると、O(N log N) に改善できます。面接ではまず O(N²) の DP を確実に書き、改善案として口頭で触れられれば十分です。

Swift 実装のポイント

dp は [Int](repeating: 1, count: nums.count) で初期値 1 のまま作れます。
内側のループは for j in 0..<i where nums[j] < nums[i] と書くと、条件が 1 行にまとまります。
答えは dp.max()! で取れます。配列は空でない制約なので ! で取り出せます。

模範解答

Swift
class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        var dp = [Int](repeating: 1, count: nums.count)
        for i in 1..<nums.count {
            for j in 0..<i where nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
        return dp.max()!
    }
}

計算量: O(N²)。