# O(n) Python Solution

• ``````class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == []:
return 0
length = len(nums)
queue = []
anwer = 1
for i in xrange(length):
while queue and queue[-1] >= nums[i]:
queue.pop()
if queue == [] or queue[-1] < nums[i]:
queue.append(nums[i])
anwer = max(anwer, len(queue))
queue = []
for i in xrange(length-1, -1, -1):
while queue and queue[-1] <= nums[i]:
queue.pop()
if queue == [] or queue[-1] > nums[i]:
queue.append(nums[i])
anwer = max(anwer, len(queue))
return anwer
``````

UPDATE:

``````class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
dpl, dpr = [0] * length, [0] * length
stack = []
for i in xrange(length):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
stack.append(i)
dpl[i] = len(stack)
stack = []
for i in xrange(length-1,-1, -1):
while stack and nums[stack[-1]] <= nums[i]:
stack.pop()
stack.append(i)
dpr[i] = len(stack)
for i in xrange(length):
``````

UPDATE:

``````class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
stack = []
length = len(nums)
unsovle = []
l = 0
for i in xrange(length):
if stack and nums[stack[-1]] == nums[i]:
continue
if not unsovle:
if not stack or nums[i] > nums[stack[-1]]:
stack.append(i)
else:
e = stack[-1]
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if not stack:
unsovle.append((0, e))
else:
unsovle.append((stack[-1], e))
while stack:
stack.pop()
stack.append(i)
else:
if nums[i] <= nums[unsovle[-1][1]]:
if not stack or nums[i] > nums[stack[-1]]:
stack.append(i)
else:
e = stack[-1]
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if not stack:
unsovle.append((0, e))
else:
unsovle.append((stack[-1], e))
while stack:
stack.pop()
stack.append(i)
else:
while unsovle and nums[unsovle[-1][1]] < nums[i]:
t = unsovle.pop()
stack.append(i)
return l
``````

Special thanks to @ccyyatnet

• can you give some explaination?

• How come it's a O(n) solution?

• wrong for [2,3,7,4,5,1,6]

• This post is deleted!

• right @ccyyatnet, thanks for letting me know that mistake, I have updated my code now :)

• Please check the updated code :)

• That one does not make sense, try to check the new one

• sorry..the new one still wrong on [2,3,1,4,5,8,6,7]

• Thanks for pointing out this issue, I have updated my code now :)

• ``````class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
stack = []
length = len(nums)
unsovle = []
l = 0
for i in xrange(length):
if stack and nums[stack[-1]] == nums[i]:
continue
if not unsovle:
if not stack or nums[i] > nums[stack[-1]]:
stack.append(i)
else:
e = stack[-1]
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if not stack:
unsovle.append((0, e))
else:
unsovle.append((stack[-1], e))
while stack:
stack.pop()
stack.append(i)
else:
if nums[i] <= nums[unsovle[-1][1]]:
if not stack or nums[i] > nums[stack[-1]]:
stack.append(i)
else:
e = stack[-1]
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
if not stack:
unsovle.append((0, e))
else:
unsovle.append((stack[-1], e))
while stack:
stack.pop()
stack.append(i)
else:
while unsovle and nums[unsovle[-1][1]] < nums[i]:
t = unsovle.pop()