## Longest Increasing Subsequence

### 描述

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.

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

### 解法1 动规

`f[j] = max{f[i], 0 <= i < j && f[i] < f[j]} + 1`

{% if book.java %}
{% codesnippet "./code/longest-increasing-subsequence-1."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% endif %}

{% if book.cpp %}
```cpp
// Longest Increasing Subsequence
// 时间复杂度O(nlogn)，空间复杂度O(n)
class Solution {
public:
int lengthOfLIS(vector& nums) {
if (nums.empty()) return 0;
// f[i]表示以i结尾的最长递增子序列的长度
vector f(nums.size(), 1);
int global = 1;
for (int j = 1; j < nums.size(); ++j) {
for (int i = 0; i < j; ++i) {
if (nums[i] < nums[j]) {
f[j] = max(f[j], f[i] + 1);
}
}
global = max(global, f[j]);
}
return global;
}
};
```
{% endif %}

### 解法2 Insert Position

{% if book.java %}
```java
// Longest Increasing Subsequence
// 时间复杂度O(nlogn)，空间复杂度O(n)
public class Solution {
public int lengthOfLIS(int[] nums) {
ArrayList lis = new ArrayList<>();
for (int x : nums) {
int insertPos = lowerBound(lis, 0, lis.size(), x);
if (insertPos >= lis.size()) {
} else {
lis.set(insertPos, x);
}
}
return lis.size();
}
private static int lowerBound (ArrayList A,
int first, int last, int target) {
while (first != last) {
int mid = first + (last - first) / 2;
if (target > A.get(mid)) first = ++mid;
else last = mid;
}

return first;
}
}
```
{% endif %}

{% if book.cpp %}
```cpp
// Longest Increasing Subsequence
// 时间复杂度O(nlogn)，空间复杂度O(n)
class Solution {
public:
int lengthOfLIS(vector& nums) {
vector lis;
for (auto x : nums) {
int insertPos = lower_bound(lis, 0, lis.size(), x);
if (insertPos >= lis.size()) {
lis.push_back(x);
} else {
lis[insertPos] = x;
}
}
return lis.size();
}
int lower_bound (const vector& A, int first, int last, int target) {
while (first != last) {
int mid = first + (last - first) / 2;
if (target > A[mid]) first = ++mid;
else last = mid;
}

return first;
}
};
```
{% endif %}