# Question

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

```
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
```

Note:

- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in \(O(n^2)\) complexity.

Follow up: Could you improve it to \(O(n log n)\) time complexity?

# \(O(n^2)\) DP Solution

```
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
```

# \(O(n log n)\) Solution

In this approach, we scan the array from left to right. We also make use of a `dp`

array initialized with all 0’s. This `dp`

array is meant to store the increasing subsequence up to and including the currently encountered element. For the element corresponding to the \(j^{th}\) index `nums[j]`

, we determine the correct position in the `dp`

array, say \(i^{th}\) index, such that `dp[:i+1]`

forms a increasing subsequence including `nums[j]`

. This can be achieved by binary search. Instead of inserting `nums[j]`

into \(i^{th}\) index of `dp`

array, we override the existing value of `dp[i]`

. We also keep track of the length of LIS so far, which would be the largest `i`

plus 1. Therefore, after traversing through `nums`

, we know the length of LIS, though the `dp`

does not store the content of it.

The time complexity is \(O(nlogn)\) because we perform \(n\) binary searches. The space complexity is \(O(n)\).

In Python, we can use `bisect`

module to perform binary search. Note that it will return the index left to the same value if the value exists in the array, so we need to handle that.

```
from bisect import bisect_left
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return len(nums)
dp = [0] * len(nums)
length = 0
for n in nums:
idx = bisect_left(dp, n, 0, length)
if idx + 1 >= len(dp) or dp[idx + 1] != n:
dp[idx] = n
if idx == length:
length += 1
return length
```