[LeetCode] 0300. Longest Increasing Subsequence

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

内容目录

Medium

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.

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
-10 ⁴ <= nums[i] <= 10 ⁴

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

Python

				
					# time complexity: O(n^2) # space complexity: O(1) from typing import List class Solution: def lengthOfLIS(self, nums: List[int]) -> int: countList = [1] * len(nums ) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: countList[i] = max(countList[i], countList[j] + 1) return max(countList) nums = [0, 1, 0, 3, 2, 3] print(Solution().lengthOfLIS(nums))

Medium

Python

相关文章