LeetCode 솔루션 분류
[8/8] 300. Longest Increasing Subsequence
본문
Medium
13979256Add to ListShareGiven an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
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.
Example 2:
Input: nums = [0,1,0,3,2,3] Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Accepted
976,302
Submissions
1,924,672
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1]*len(nums)
for i in range(len(nums)-1, -1, -1):
max_lis = 0
for j in range(i+1, len(nums)):
if nums[i] < nums[j]:
max_lis = max(dp[j], max_lis)
dp[i] = max_lis + 1
return max(dp)
