最长递增子序列（LIS）

问题描述：
求一个序列的最长递增子序列，这样的子序列是允许中间越过一些字符的，即留“空”。


例如：4 2 3 1 5 的最长递增子序列为 2 3 5，长度为 3 。


解法：
这里给出两种动态规划的做法，第二种是比较优化的 dp 。


① dp：dp[i] 表示以 i 结尾的最长递增子序列长度。


第一个元素直接设置 LIS 长度为 1 即可。


处理第二个元素 2 的时候判断是否比前面的元素 4 大，没有的话那么以 2 为结尾的 LIS 就是 2，


即 LIS 长度为 1。


处理第三个元素 3 的时候需要跟前面的每个元素都进行比较，3 大于 2，则 LIS 的长度可能为 dp[1] + 1，


3 小于 4，则 LIS 的长度可能为 1，比较dp[1] + 1 和 1，取最大值，为 2 。


处理第四个元素 1，发现比前面的元素都小，那么以 1 为结尾的 LIS 只可能为 1，因此 LIS 的长度为 1。


处理最后一个元素 5，发现比前面的元素都大，那么以 5 结尾的 LIS 的长度可能为


dp[0] + 1，dp[1] + 1，dp[2] + 1，dp[3] + 1。


其中的最大值为 dp[2] + 1 = 3，因此 LIS 的长度为 3。


总结：


dp[i] 默认都为 1，因为以 i 结尾的 LIS 至少包含自己。


在 dp 表 0~i-1 中比对时，若 arr[i] > arr[j]，


那么 dp[j] + 1 可能为 dp[i] 的最终值。


需要在所有的可能值中取最大值。


时间复杂度为 O(n2)。


② dp：dp[i] 表示长度为 i 的最长递增子序列（LIS）末尾的数。


第一个元素直接加入 dp 表，dp[1] = 4，表示长度为 1 的 LIS 末尾的数当前为 4。


第二个元素为 2，因为 2 < 4，直接替换掉 4，dp[1] = 2 。


因为后面序列中的数字 > 2 的几率一定比 > 4 的几率高，有种贪心的感觉。


第三个元素为 3，由于 3 > dp[1] = 2，构成递增，dp[2] = 3，表示长度为 2 的 LIS 的末尾为 3 。


第四个元素为 1，由于 1 < dp[2] = 3，因此在前面一定有一个位置可以换成 1，


并且后面的递增性质不会被破坏。


第一个 > 1 的为 dp[1] = 2，因此将 dp[1] 置为 1。


最后一个元素为 5， 5 > dp[2] = 3，构成递归，故dp[3] = 5。


全部遍历完成，这个时候我们就可以发现 dp 数组的下标 3 就是我们要求的 LIS 长度。


参考代码：


// 这里的最长递增子序列是允许中间跨越其他子序列的 
#include
#include
using namespace std;


int *arr;
int *dp;


// 经典问题 dp[i]的意思为以i为结尾的最长子序列为多少 
int getResult(int n){
dp[0] = 1;
for(int i = 0; i < n; i++){
int cnt = 1;
for(int j = i-1; j >= 0; j--){
if(arr[i] > arr[j]){  // 保证递增 
cnt = max(cnt, dp[j]+1);
}
}
dp[i] = cnt;
}
int ans = 0;
for(int i = 0; i < n; i++){
ans = max(ans, dp[i]);
}
return ans;
}


// 二分查找变体 找到第一个大于n的位置index 
int BinarySearch(int *dp, int len, int n){
int left = 1;
int right = len;
while(left < right){
int mid = (left+right)/2;
if(dp[mid] > n){
right = mid;
}
else{
left = mid+1;
}
}
return right;
}


// 优化的dp dp数组的最终下标为答案 
int getResult1(int n){
dp[1] = arr[0];
int index = 1;
for(int i = 1; i < n; i++){
if(arr[i] > dp[index]){
// 更新index 
dp[++index] = arr[i];
}
else{
// 把dp数组中第一个大于n的数字替换为arr[i] 
int tempIndex = BinarySearch(dp, index, arr[i]);
dp[tempIndex] = arr[i];
}
}
return index;
} 


int main(){
int n;
while(cin >> n){
arr = new int[n];
dp = new int[n+1];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
int ans = getResult1(n);
cout << ans << endl;
delete[] arr;
delete[] dp;
}
return 0;
} 

————————————————
版权声明：本文为CSDN博主「未已优」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41765114/article/details/88415541