# Longest Increasing Subsequence Problem
https://leetcode.com/problems/longest-increasing-subsequence/
- Equivalent to longest northeast problem (in [[computational-geometry]])
- Resources
- [Longest Increasing Subsequence (LIS) | GeeksforGeeks](https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/)
- [Longest increasing subsequence | Wikipedia](https://en.wikipedia.org/wiki/Longest_increasing_subsequence)
- [Longest increasing subsequence | Algorithms for Competitive Programming](https://cp-algorithms.com/sequences/longest_increasing_subsequence.html)
- Procedure ([handwritten note](https://notability.com/n/f91v_oq4EIOtEKgPPfMqY))
- Start from initial point $s$, use [[sweeping]] method.
- Find the first point that forms a increasing sub-sequence, mark it with
number 1.
- Upon finding another point, if it extends from the previous point on path,
mark it with number 2, and keep a pointer to the previous point on path.
- Upon finding a lower point that can be used to form a path with length of 2,
insert it into our state, and delete all the previous one that are higher.
They're no longer useful anyway.
## Approach 1: [[dp|DP]]
- `dp[i]` represents the length of LIS that ends at `i`.
- `dp[0] = 1` as base condition.
- For each `nums[j]` before `nums[i]`, if that element is smaller than `nums[i]`, we can extend `dp[i]` to `dp[j] + 1` (if it's indeed larger) using `nums[j] -> nums[i]`.
- Repeat the process.
```python
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
```
- Time complexity: $O(n^2)$
## Approach 2: Intelligently Building Subsequence
- If the `num` is greater the `sub[-1]`, just append it to extend the subsequence.
- Otherwise, iterate through `sub` and find the first element that is greater than `num`, and replace them.
- The idea is, replacing this number allows future `num`'s encountered to be also included to extend the subsequence.
- The resulting subsequence is not a valid one, but the length of it matches LIS.
```python
sub = [nums[0]]
for num in nums[1:]:
if num > sub[-1]:
sub.append(num)
else:
i = 0
while num > sub[i]:
i += 1
sub[i] = num
return len(sub)
```
- Time complexity: $O(n^2)$
## Approach 3: Subsequence Building with [[binary-search]]
For `bisect_left`, `all(elem < x for elemin a[lo : ip])`.
```python
sub = []
for num in nums:
i = bisect_left(sub, num)
if i == len(sub):
sub.append(num)
else:
sub[i] = num
return len(sub)
```
Time complexity: $O(n\lg n)$.