[LeetCode] 0300. Longest Increasing Subsequence

/ Leetcode, 技術文章 / 作者:
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
  • -104 <= nums[i] <= 104

 

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))

相關文章