【LeetCode】300. Longest Increasing Subsequence 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python, DP
2. 解答2：Python, DP + Binary Search
メモ・参考・感想

問題

原文

Given an integer array nums, return the length of the longest strictly increasing

subsequence

.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

1
2
3

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3] Output: 4

1
2

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7] Output: 1

1
2

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500

-10⁴ <= nums[i] <= 10⁴

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

内容

整数配列numsが与えられるので、厳密に増加する最長の部分配列を返してください。

※部分配列は各要素が連続していなくても良い

※正しくない可能性があります。

解答

解答1：Python, DP

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [0 for _ in range(len(nums))]
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp) + 1

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

dp = [0 for _ in range(len(nums))]

for i in range(1, len(nums)):

for j in range(i):

if nums[j] < nums[i]:

dp[i] = max(dp[i], dp[j] + 1)

return max(dp) + 1

time:O(n^2)

space:O(n)

解答2：Python, DP + Binary Search

#https://leetcode.com/problems/longest-increasing-subsequence/solutions/2395570/python3-7-lines-binsearch-cheating-w-explanation-t-m-94-82/


import bisect
class Solution:                 
    def lengthOfLIS(self, nums: list[int]) -> int:
        #dp配列を用意。numsの1つ目の要素だけ入れておく
        dp = [nums.pop(0)]
        #numsを順に処理
        for n in nums: 
            #dpの最後の要素よりnが大きい場合                      
            if n > dp[-1]:                  
                #dp配列にnを追加
                dp.append(n)
            #dp配列内で、nよりも小さい要素とnを入れ替える
            #入れ替えではなく追加してしまうと、仮にnums[2,5,3,7]の場合、dp=[2,5,3となる]
            #dp=[2,3,7]となってほしい。(dp=2,5,7)でも問題はなさそう
            else:       
                dp[bisect_left(dp, n)] = n 
        return len(dp)

#https://leetcode.com/problems/longest-increasing-subsequence/solutions/2395570/python3-7-lines-binsearch-cheating-w-explanation-t-m-94-82/

import bisect

class Solution:

def lengthOfLIS(self, nums: list[int]) -> int:

#dp配列を用意。numsの1つ目の要素だけ入れておく

dp = [nums.pop(0)]

#numsを順に処理

for n in nums:

#dpの最後の要素よりnが大きい場合

if n > dp[-1]:

#dp配列にnを追加

dp.append(n)

#dp配列内で、nよりも小さい要素とnを入れ替える

#入れ替えではなく追加してしまうと、仮にnums[2,5,3,7]の場合、dp=[2,5,3となる]

#dp=[2,3,7]となってほしい。(dp=2,5,7)でも問題はなさそう

else:

dp[bisect_left(dp, n)] = n

return len(dp)

time:O(nlog(n))

space:O(n)

bisectを使うと通るが、自分で二分探索を書いて実行するとエラーになるケースがあり未解決。

dp配列内でどこに要素を入れるかを探索するときに二分探索を使うことで、時間計算量がO(n^2)からO(log(n))に改善

問題文よりdp配列は昇順となるように要素が追加される実装になるので、もともとソートされている。

メモ・参考・感想

前：413. Arithmetic Slices

次：2351. First Letter to Appear Twice

LeetCode 解答・解説記事一覧