Medium - Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/

Longest Increasing Subsequence - LeetCode

문제 설명

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

Constraints:

• 1 <= nums.length <= 2500
• -10 ** 4 <= nums[i] <= 10 ** 4

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

예시

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.

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

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

풀이

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

0 <= a < b < len(nums) 일 때, nums[b] > nums[a]를 만족하는 b - a + 1의 최대값을 구하는 문제.

위의 풀이는 O(n) = n ** 2인 일반적인 풀이다.

Subsequence의 길이의 최소값인 1로 세팅해둔 table을 만들고, 루프를 돈다. for i in range(length)

루프 안에서 또 한 번 루프를 돌면서, for j in range(i)

nums[i] 가 nums[j]보다 작거나 같은 경우는 무시하고, 아니라면 table[j] + 1 (0 <= j < i) 의 최대값을 구해서 table[i]에 입력한다.

루프를 마친 후, max(table)로 i번째에서 마무리한 Subsequence 중 최대값을 찾는다.

 

문제 설명의 마지막 단에

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

n log(n)을 보니 Sort로 풀이가 있나 싶어서 sorted((val, i) for i, val in enumerate(nums))를 사용한 풀이를 생각해봤는데, 방법이 생각나지 않는다. 뭘까,,,