[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

相關文章