# Longest Increasing Subsequence
`Dynamic Programming`, `Binary Search`
**Medium**
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(nlogn) time complexity?
## Analysis
[https://leetcode.com/problems/longest-increasing-subsequence/solution/](https://leetcode.com/problems/longest-increasing-subsequence)
### Naive Approach & Intuition
**Brute-Force (TLE) - O(2^n) time**
recursively search: include or not include the next position, and find the maximum of them
**Recursive with Memoization (MLE)**
same as above, but stores intermediate results, thus reduce the repetitive search; however, will exceed memory limit
### **Dynamic Programming - O(n^2) time, O(n) space**
**State:**
`dp[i]` - represents the **length** of the longest increasing subsequence possible considering the array elements up to the i-th index only, by necessarily including the i-th element.
即以i-th元素结尾，并且包含i-th元素的最长上升子序列的长度
**State Transfer Function:**
`dp[i] = max(dp[j]) + 1,∀ 0 ≤ j < i`
To calculate `dp[i]`, we need to append current element (`nums[i]` ) for all possible `nums[i] > nums[j]` where `j` is one of
`0, 1, 2, ..., i - 1`
**Initialization:**
`dp[0] = 1;`
`max = 1;`
Since single element is considered as LIS of length 1
**Final Answer:**
`LIS_length = max(dp[i]), ∀ 0 ≤ i < n`
即循环遍历`dp[i]`以找到其中最大值
### **Dynamic Programming with Binary Search - O(nlogn) time, O(n) space**
From Source:
@dietpepsi
`tails[i]` - **tails** is an array storing the **smallest tail** of all increasing subsequences with length `i+1` in `tails[i]`.
For example, say we have `nums = [4,5,6,3]`, then all the available increasing subsequences are:
```
len = 1 : [4], [5], [6], [3] => tails[0] = 3
len = 2 : [4, 5], [5, 6] => tails[1] = 5
len = 3 : [4, 5, 6] => tails[2] = 6
```
Three scenarios on updating the ending (tail) numbers array:
```
(1) if x is larger than all tails, append it, increase the size by 1
(2) if x is smaller than the tails[0], then update tails[0]
(3) if tails[i-1] < x <= tails[i], update tails[i]
```
From Source:
按照以下规则更新这些序列\
– 如果`nums[i]`比所有序列的末尾都大，或等于最大末尾，说明有一个新的不同长度序列产生，我们把最长的序列复制一个，并加上这个`nums[i]`。\
– 如果`nums[i]`比所有序列的末尾都小，说明长度为1的序列可以更新了，更新为这个更小的末尾。\
– 如果在中间，则更新那个末尾数字刚刚大于等于自己的那个序列，说明那个长度的序列可以更新了。
## Solution
#### Dynamic Programming - O(n^2) time, O(n) space
```java
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
dp[0] = 1;
int max = 1;
for (int i = 1; i < n; i++) {
int prevMax = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
prevMax = Math.max(dp[j], prevMax);
}
}
dp[i] = prevMax + 1;
max = Math.max(dp[i], max);
}
return max;
}
}
```
#### DP - O(n^2) time, O(n) space -- Easier to understand version
14 ms, faster than 49.36%
```java
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxAns = 1;
for (int i = 1; i < dp.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxAns = Math.max(maxAns, dp[i]);
}
return maxAns;
}
}
```
#### Dynamic Programming with Binary Search - O(nlogn) time, O(n) space
0ms, faster than 100%
```java
class Solution {
public int lengthOfLIS(int[] nums) {
// nlogn
if (nums.length == 0) {
return 0;
}
// `tails[i]` is an array of the ending numbers of LIS with length of i + 1
int[] tails = new int[nums.length];
tails[0] = nums[0];
// `len` means the actual LIS length - 1, it's more convenient for array index
int len = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > tails[len]) {
tails[++len] = nums[i];
} else if (nums[i] < tails[0]) {
tails[0] = nums[i];
} else {
int index = binarySearch(tails, len, nums[i]);
tails[index] = nums[i];
}
}
return len + 1;
}
private int binarySearch(int[] arr, int len, int num) {
int l = 0, r = len;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] < num) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
}
```
DP + Binary Search With Comment
```java
public class Solution {
public int lengthOfLIS(int[] nums) {
// write your code here
if(nums.length == 0){
return 0;
}
// len表示当前最长的升序序列长度（为了方便操作tails我们减1）
int len = 0;
// tails[i]表示长度为i的升序序列其末尾的数字
int[] tails = new int[nums.length];
tails[0] = nums[0];
// 根据三种情况更新不同升序序列的集合
for(int i = 1; i < nums.length; i++){
if(nums[i] < tails[0]){
tails[0] = nums[i];
} else if (nums[i] > tails[len]){
tails[++len] = nums[i];
} else {
// 如果在中间，则二分搜索
tails[binarySearch(tails, 0, len, nums[i])] = nums[i];
}
}
return len + 1;
}
private int binarySearch(int[] tails, int min, int max, int target){
while(min <= max){
int mid = min + (max - min) / 2;
if(tails[mid] == target){
return mid;
}
if(tails[mid] < target){
min = mid + 1;
}
if(tails[mid] > target){
max = mid - 1;
}
}
return min;
}
}
```
## Reference
LeetCode discussion:
LeetCode Official Solution:
GeeksforGeeks - N log N time:
Yanjia:
Grandy Yang: