def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# hashmap key:the max subsequence before this number / value:list of the nums with this step read before
# if this number bigger than anyone number with the max steps of subsequence, it will add one key +1 to the hashmap
# for example: [10, 9, 2, 5, 3, 7, 101, 18]
# when it comes to 7, hashmap before: {1: [10, 9, 2], 2: [5, 3]}  hashmap after: {1: [10, 9, 2], 2: [5, 3], 3: [7]}
l = len(nums)
if l == 0:
return 0
hash = {1:[]}
bigkey = 1
for i in range(l):
# print hash
key = bigkey
while(key>=1):
if len(list(filter(lambda x:x<nums[i],hash[key]))) >0:
key = key +1
if key>bigkey: bigkey = key
if key in hash:
hash[key].append(nums[i])
else:
hash[key] = [nums[i]]
break
else:
key = key1
if key == 0:
hash[1].append(nums[i])
return bigkey
Python using hashmap with explanation


Sorry for that.
class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """ # hashmap key:the max subsequence before this number / value:list of the nums with this step read before # if this number bigger than anyone number with the max steps of subsequence, it will add one key +1 to the hashmap # for example: [10, 9, 2, 5, 3, 7, 101, 18] # when it comes to 7, hashmap before: {1: [10, 9, 2], 2: [5, 3]}  hashmap after: {1: [10, 9, 2], 2: [5, 3], 3: [7]} l = len(nums) if l == 0: return 0 hash = {1:[]} bigkey = 1 for i in range(l): print hash key = bigkey while(key>=1): if len(list(filter(lambda x:x<nums[i],hash[key]))) >0: key = key +1 if key>bigkey: bigkey = key if key in hash: hash[key].append(nums[i]) else: hash[key] = [nums[i]] break else: key = key1 if key == 0: hash[1].append(nums[i]) return bigkey
And an example running result is attached:
Your input[10,9,2,5,3,7,101,18]
Your stdout
{1: []}
{1: [10]}
{1: [10, 9]}
{1: [10, 9, 2]}
{1: [10, 9, 2], 2: [5]}
{1: [10, 9, 2], 2: [5, 3]}
{1: [10, 9, 2], 2: [5, 3], 3: [7]}
{1: [10, 9, 2], 2: [5, 3], 3: [7], 4: [101]}