# Share my Python Solution beating 90.36% (Patience (greedy) & DP)

• Method1: Dynamic Programming O(n^2) 16.38%

• I construct a list f, which store the LIS of each element.
• At each element, I compare it with the former element to find the LIS.
• With the spirit of DP, I can insure that if I know nums[i-1]'s LIS, I can know nums[i]'s LIS.
``````class Solution(object):
def lengthOfLIS(self, nums):
if not nums or len(nums) == 1: return len(nums)
f = [1] * len(nums)

for i in xrange(1, len(nums)):
for j in xrange(i):
if nums[i] > nums[j]:
f[i] = max(f[i], f[j] + 1)

return max(f)
``````

Method2: Patience: Greedy Algorithm O(nlog(n)) 90.36%

• I construct a list f, which stores piles of substring in decreasing order.
• Since I would not find the LIS itself and just find the length of LIS, f only stores the last element (smallest one) of each pile.
• In the iteration, if nuts[i] > f[-1], directly append nuts[i] to the end of f
• else, we use binary search to find the position, which nuts[i] belongs to, and replace it with nuts[i].
``````class Solution(object):
def lengthOfLIS(self, nums):
if not nums: return 0
f = [nums[0]]

for i in xrange(1, len(nums)):
# If nums[i] > the end of f, append nums[i] to f.
if nums[i] > f[-1]: f.append(nums[i])
else:
# binary search
begin, end = 0, len(f)
while begin < end:
mid = (begin + end) / 2
if nums[i] == f[mid]:
begin = mid
break
if nums[i] > f[mid]:
begin = mid + 1
else: end = mid
f[begin] = nums[i]
return len(f)
``````

Greedy using python bisect (more concise)

``````import bisect
class Solution(object):
def lengthOfLIS(self, nums):
if not nums: return 0
f = [nums[0]]

for i in xrange(1, len(nums)):
if nums[i] > f[-1]: f.append(nums[i])
else:
pos = bisect.bisect_left(f, nums[i])
f[pos] = nums[i]
return len(f)
``````

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