> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/dynamic_programming/longest-increasing-subsequence.md).
# 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: [https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation](https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O%28nlogn%29-time-with-explanation)
@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: [https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation](https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O%28nlogn%29-time-with-explanation)
LeetCode Official Solution:
GeeksforGeeks - N log N time:
Yanjia:
Grandy Yang:
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/longest-increasing-subsequence.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.