最长递增子序列(LIS)
最长递增子序列(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<iostream>
#include<algorithm>
using namespace std;
int *arr;
int *dp;
// 经典问题 dp[i]的意思为以i为结尾的最长子序列为多少
int getResult(int n)
{
dp[0] = 1;
for (int i = 1; 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;
}
【END】感谢观看
INF_512: 引用「对于不知道方向的边 u − v u-vu−v,满足 ∣ a u − a v ∣ = = 1 |a_u」 根据 a_u - a_v <= 1, a_v - a_u <= 1, 说明有可能 |a_u - a_v| == 0,不满足 |a_u - a_v| == 1了,但执行结果却是对的,有大佬能说说为什么吗?
廿七359: 这里求得其实是以1为结尾的递增子序列,没有比1大的数,所以长度是1,你说的2是以3为结尾的递增子序列
快乐啦啦啦啦啦: 为啥4 2 3 1 的最长递增子序列长度是1啊,2,3不是递增子序列吗,长度应该是2啊
o荷塘月色o: 第一种方法非常棒!很像合唱队问题的解法。另外这题可以转成和排序好的数组寻找LTS,也很方便。
沉默的abbot: 第三个问题,容量是5,只能选第一个的时候,为什么不能选两个体积是2的,价格是6,又没说只能选一个