[ LeetCode - 300 ] Longest Increasing Subsequence

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

Longest Increasing Subsequence - LeetCode

 

Dynamic Programming 문제로 이전 까지의 누적된 값을 가지고 다음 값을 구해야 하는 문제다.

처음에는 테이블 없이 할 수 있을줄 알았는데 다른 인덱스의 누적 값도 알아야 풀 수 있는 문제였다...

 

문제를 이해하는데 있어서 필요한건 이 문제는 substring 같은 인접한 요소를 고려하는게 아니라 순서를 보는 것이다.

example)
[1, 3, 2, 4] 의 경우 1과 2 사이에 3이 껴있지만 1, 2, 4는 증가하는 부분 수열을 만들 수 있기 때문에 정답 3이 된다. 

---

[ 📌 풀이 ]

1. 먼저 리스트를 순회하기 위해서 인덱스를 뽑는 반복문을 돌리고, 두 번째 반복문으로 해당 인덱스까지 반복한다. (2중 for문)

2. 조건문이 참이면 현재 순회중인 인덱스 i에 해당하는 값 dp[i] 갱신한다.

(조건문 - 현재 순회중인 요소 nums[i]가 커야만 부분 수열이 더 커질 가능성이 있기 때문이다)

 

dp[i] 의미: 인덱스 'i' 까지의 부분 수열의 최대 크기

[ 문제 첫 번째 Example 시각화 ]

---

[ 📌 코드 - Python ]

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

s = Solution()
result = s.lengthOfLIS([10,9,2,5,3,7,101,18])

print(result)

---

[ 📌 결과 ]

[ Result ]