引言
不知道为啥上次放在LCS最后的LIS转LCS的方法在上机题中WA掉了，匆忙之下复制粘贴了别人的板子，感觉很罪恶，还是得总结一下属于自己的板子
O(n 2)
分析：我们假设dp[i]表示以arr[i]结尾的最长上升子序列的长度，那么dp[i]就有可能从任何满足 arr[j] < arr[i] 的dp[j]转移来，只需在dp[i]和dp[j] + 1之间取最大值就好了，而这只是对于arr中的任意i所做的操作，最后要得到结果，我们还得在dp[1]到dp[i]中挑出最大值，即为最终答案，详见代码（为了格式化代码，所有变量声明在全局）：
输入
void scan(){
for(int i
= 1;i
<= n
;i
++){
scanf("%d", &arr
[i
]);
}
}
初始化
void init(){
ans
= 0;
for(int i
= 1;i
<= n
;i
++){
dp
[i
] = 1;
}
}
DP
void DP(){
for(int i
= 1;i
<= n
;i
++){
for(int j
= 1;j
< i
;j
++){
if(arr
[j
] < arr
[i
]){
dp
[i
] = max(dp
[i
],dp
[j
] + 1);
}
}
ans
= max(ans
,dp
[i
]);
}
}
输出
void print(){
printf("%d\n", ans
);
}
O(nlogn)
分析：我们这样想一下，在对arr数组扫描的过程中，如果一个单调上升子序列的最后一个元素越小，那么就越有利于在后面接上元素，那么单调上升子序列就会更容易变长，于是用一个low数组，low[i]记录长度为i的单调上升子序列的最后一个元素，可以证明，扫描进行到最后得到的low数组长度，就是最长上升子序列的长度。思路：对于每个arr[i]，如果arr[i] > low[ans]，则low[ans++] = arr[i]，否则在low数组中找到第一个大于等于arr[i]的元素，然后用arr[i]替换之
输入
初始化
void init(){
ans
= 1;
}
OP
void OP(){
low
[1] = arr
[1];
for(int i
= 2;i
<= n
;i
++){
if(arr
[i
] > low
[ans
]){
low
[++ans
] = arr
[i
];
}
else{
int tmp
= lower_bound(low
+ 1,low
+ ans
,arr
[i
]) - low
;
low
[tmp
] = arr
[i
];
}
}
}
输出
对比（十分明显）
