**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)
```