Longest Increasing Subsequence
문제
- 정수 리스트
nums
- 가장 긴 증가하는 subseq
풀이
- 전에 백준에서 많이 풀어본 dp
- subseq의 시작점과 끝점이 다양할 수 있음을 유의
- O(n**2)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
lenNums = len(nums)
dp = [1 for _ in range(lenNums)]
for i in range(1, lenNums):
for j in range(i):
if nums[j] < nums[i] and dp[j] >= dp[i]:
dp[i] = dp[j]+1
return max(dp)
결과
nums
- 전에 백준에서 많이 풀어본 dp
- subseq의 시작점과 끝점이 다양할 수 있음을 유의
- O(n**2)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
lenNums = len(nums)
dp = [1 for _ in range(lenNums)]
for i in range(1, lenNums):
for j in range(i):
if nums[j] < nums[i] and dp[j] >= dp[i]:
dp[i] = dp[j]+1
return max(dp)
결과
Author And Source
이 문제에 관하여(Longest Increasing Subsequence), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@twinklesu914/Longest-Increasing-Subsequence저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)