Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [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.
Note:
There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
My code:
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)<=1:
return len(nums)
self.max_length=0
self.record=[-1]*len(nums)
self.check_longest(nums,len(nums)-1)
return self.max_length
def check_longest(self,nums,j):
if j==0:
return 1
if self.record[j]!=-1:
return self.record[j]
local_max=1
for k in range(j):
if nums[j]>nums[k]:
count=self.check_longest(nums,k)
local_max=max(local_max,count+1)
else:
count=self.check_longest(nums,k)
self.max_length=max(self.max_length,count)
self.record[j]=local_max
self.max_length=max(self.max_length,self.record[j])
return self.record[j]
Solution: https://leetcode.com/problems/longest-increasing-subsequence/submissions/