# Python using hashmap with explanation

• 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 = key-1
if key == 0:
hash[1].append(nums[i])
return bigkey

• 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 = key-1
if key == 0:
hash[1].append(nums[i])
return bigkey
``````

And an example running result is attached:

[10,9,2,5,3,7,101,18]

{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]}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.