0300 Longest Increaseing Subsequence#
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?
Dynamic programming solves this problem in
Binary search can be used here to perform
def lengthOfLIS(nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
# test on typical cases
print(lengthOfLIS([10,9,2,5,3,7,101,18]))
print(lengthOfLIS([1,3,6,7,9,4,10,5,6]))
print(lengthOfLIS([1,2,3,4,5,6,7,8,9]))
print(lengthOfLIS([9,8,7,6,5,4,3,2,1]))
print(lengthOfLIS([1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9]))
4
6
9
1
9
# use binary search within patience sort
def lengthOfLIS(nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
# top of each pile in the patience sort
# dp is sorted in ascending order
dp = [nums[0]]
for i in range(1, len(nums)):
if nums[i] > dp[-1]:
dp.append(nums[i])
else:
# binary search to find the leftmost element (smallest) in piles that is larger than nums[i]
l, r = 0, len(dp)-1
while l <= r:
mid = (l+r)//2
# move right
if dp[mid] < nums[i]:
l = mid + 1
# move left
else:
r = mid - 1
dp[l] = nums[i]
return len(dp)
# test
print(lengthOfLIS([10,9,2,5,3,7,101,18]))
print(lengthOfLIS([1,3,6,7,9,4,10,5,6]))
print(lengthOfLIS([1,2,3,4,5,6,7,8,9]))
print(lengthOfLIS([9,8,7,6,5,4,3,2,1]))
print(lengthOfLIS([1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9]))
4
6
9
1
9