# Longest Increasing Subsequence

## Question

### Problem Statement

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

For example,

Given [10, 9, 2, 5, 3, 7, 101, 18],

The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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.

Could you improve it to $O(n \log n)$ time complexity?

#### Credits:

Special thanks to @pbrother for adding this problem and creating all test cases.

## 题解1 - 双重 for 循环

### Python

class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return 0

lis = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i] and lis[i] < 1 + lis[j]:
lis[i] = 1 + lis[j]
return max(lis)


### C++

class Solution {
public:
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> nums) {
if (nums.empty()) return 0;

int len = nums.size();
vector<int> lis(len, 1);

for (int i = 1; i < len; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i] && (lis[i] < lis[j] + 1)) {
lis[i] = 1 + lis[j];
}
}
}

return *max_element(lis.begin(), lis.end());
}
};


### Java

public class Solution {
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
public int longestIncreasingSubsequence(int[] nums) {
if (nums == null || nums.length == 0) return 0;

int[] lis = new int[nums.length];
Arrays.fill(lis, 1);

for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && (lis[i] < lis[j] + 1)) {
lis[i] = lis[j] + 1;
}
}
}

// get the max lis
int max_lis = 0;
for (int i = 0; i < lis.length; i++) {
if (lis[i] > max_lis) {
max_lis = lis[i];
}
}

return max_lis;
}
}


### 源码分析

1. 初始化数组，初始值为1
2. 根据状态转移方程递推求得lis[i]
3. 遍历lis 数组求得最大值

## 题解2 - 巧用 lower_bound

### C++

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;

vector<int> lis;
for (int i = 0; i < nums.size(); ++i) {
vector<int>::iterator it = lower_bound(lis.begin(), lis.end(), nums[i]);
if (it == lis.end()) {
lis.push_back(nums[i]);
} else {
*it = nums[i];
}
}

return lis.size();
}
};


## 题解1 - LIS

### Java

import java.util.*;

public class Solution {
/**
* @param nums: The integer array
* @return: LIS array
*/
public int[] longestIncreasingSubsequence(int[] nums) {
if (nums == null || nums.length == 0) return null;

int[] lis = new int[nums.length];
Arrays.fill(lis, 1);

for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] <= nums[i] && (lis[i] < lis[j] + 1)) {
lis[i] = lis[j] + 1;
}
}
}

// get the max lis
int max_lis = 0, index = 0;
for (int i = 0; i < lis.length; i++) {
if (lis[i] > max_lis) {
max_lis = lis[i];
index = i;
}
}

// get result
int[] result = new int[max_lis];
for (int i = index; i >= 0; i--) {
if (lis[i] == max_lis) {
result[max_lis - 1] = nums[i];
max_lis--;
}
}

return result;
}

public static void main(String[] args) {
int[] nums = new int[]{5, 4, 1, 2, 3};
Solution sol = new Solution();
int[] result = sol.longestIncreasingSubsequence(nums);
for (int i : result) {
System.out.println(i);
}
}
}