动态规划+二分：
dp[i]：dp数组表示（在数组dp中）以i结尾的最长序列的元素。
例如 arr = [ 1, 3, 2 ] 则 dp = [ 1, 2 ] 即长度为1的序列最后的元素为1，长度为2的序列最后元素为2。
maxlen[i]：表示(在数组arr中)以i结尾的最长序列的长度。
算法流程：我们在遍历arr的时候
- 当arr[i] >dp.back() 此时把arr[i]放入dp，表示我们找到了一条更长的子序列,并更新对应i下maxlen的长度。
- 否则，需要找到dp数组里面第一个大于等于arr[i]的元素，更新该元素。并且插入maxlen为找到这个元素所对应的子序列长度
这里以 arr = [ 1,4,6,3 ]为例：
当放入1：dp[1],max[1]
当放入4：dp[1,4],max[1,2]
当放入6：dp[1,4,6],max[1,2,3] //这里对应算法流程的第一步
当放入3：dp[1,3,6],max[1,2,3,2] //这里对应算法流程的第二步，我们很容易发现当前的dp数组并不是一个正确的序列，所以dp并不是最后的结果数组，dp数组只是表示长度为n长度最长序列的最后元素，也就是最长为2的最后元素为3，最长为3的最后元素为6
最后我们逆序遍历max数组，从dp的长度开始，该例中为3，找到各个位置的元素，这里逆序的原因我们很容易想到，是因为后面的元素，我们都是往字典序小的方向更新的。
#include <algorithm>
#include <cstdio>
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* retrun the longest increasing subsequence
* @param arr int整型vector the array
* @return int整型vector
*/
vector<int> LIS(vector<int>& arr) {
// write code here
vector<int> res;
const int len = arr.size();
if (!len) return res;
vector<int> dp;
vector<int> maxlen;
dp.emplace_back(arr[0]);
maxlen.emplace_back(1);
for (int i = 1; i < len; i++) {
if (arr[i] > dp.back()) {
dp.emplace_back(arr[i]);
maxlen.emplace_back(dp.size());
}
else {
int index = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
dp[index] = arr[i];
maxlen.emplace_back(index + 1);
}
}
int end = len - 1;
while (maxlen[end] != dp.size()) {
end--;
}
res.resize(dp.size());
int cur_len = dp.size();
while (end >= 0) {
if (maxlen[end] == cur_len) {
res[cur_len - 1] = arr[end];
cur_len--;
}
end--;
}
return res;
}
};