動的計画法:最長増加部分列(LIS)

· algorithms, python

問題

整数配列が与えられたとき、狭義に単調増加する最長部分列の長さを返します。

タビュレーション(O(n^2))

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)