上升子序列:从一个序列中按照顺序挑出一些数，使得后一个数大于前一个数
例如对于序列$$1,5,3,7,7,2$$
$$1,5,7$$ $$5,7$$ $$1,3$$都是其上升子序列
但是$$1,5,7,7$$不是上升子序列(不满足后一个数大于前一个数)
最长上升子序列:一个序列中最长的上升子序列
对于序列$$1,5,3,7,7,2$$ 其最长上升子序列是$$1,3,7$$或者$$1,5,7$$
求最长上升子序列的算法
1.朴素的O(n²)的动态规划
设dp[tail]为序列中以第tail个元素结尾的最长上升子序列的长度
则有dp[1]=1 (第一个数自成一个最长上升子序列)
tail>1时$$dp[tail]=max\{0,dp[1],dp[2],dp[3]…dp[i]…dp[tail-1]|满足seq[i]<seq[tail]\}+1$$
结果为$$max{dp[i]|1<=i<=序列长度}$$
解释:求dp[tail]时,从序列中tail前的所有数中找到比seq[tail]小的数,在满足这个数比seq[tail]小的情况下使dp[tail]最大
举例:对于序列
$$1,5,3,2,5,6$$
使用seq[1]表示序列中的第一项,seq[2]表示序列中的第二项,以此类推
初始时dp[1]=1;
然后开始求dp[2] 发现seq[1]<seq[2] 所以dp[2]=dp[1]+1=2
开始求dp[3] 发现seq[1]<seq[3] 更新dp[3]=dp[1]+1=2
开始求dp[4] 发现seq[1]<seq[4] 更新dp[4]=dp[1]+1=2;
开始求dp[5] 发现seq[1]<seq[5] 更新dp[5]=dp[1]+1=2
又发现seq[3]<seq[5] 再次更新dp[5]=dp[3]+1=3
开始求dp[6] 发现seq[1]<seq[6] 更新dp[6]=dp[1]+1=2
又发现seq[2]<seq[6] 更新dp[6]=dp[2]+1=3
又发现seq[3]<seq[6] 更新dp[6]=dp[3]+1=3
以此类推
最终 dp[1]=1 dp[2]=2 dp[3]=2 dp[4]=2 dp[5]=3 dp[6]=3
最终结果为3
程序:
#include
using namespace std;
typedef long long int_t;
int_t seq[1001];
int_t dp[1001];
int main() {
dp[1] = 1;
int_t n;
cin>>n;
for (int_t i = 1; i <= n; i++) cin >> seq[i];
//一次性计算出LIS
for (int_t i = 1; i <= n; i++) {
int_t length = 0;
for (int_t j = 1; j <= i; j++) { if (seq[i] > seq[j]) {
if (dp[j] > length) length = dp[j];
}
}
dp[i] = length + 1;
}
int_t result = 0;
for (int_t i = 1; i <= n; i++) {
result = max(result, dp[i]);
}
cout << result;
return 0;
}
2.复杂度为O(n log n)的算法
设dp[i]为以序列中第i个元素结尾的最长上升子序列的长度，那么如果对于序列中任意两个数seq[i]和seq[j] 如果满足dp[i]==dp[j]且seq[i]<seq[j] 那么仅保存i一定不会丢失最优解(因为seq[i]<seq[j],所以可以接到seq[j]后面的数一定可以接到seq[i]后面，然而可以接到seq[i]后面的数却不一定能接到seq[j]后面)
设g[x]为满足dp[i]==x的最小的seq[i]
下一句的最长上升子序列长度是指以该数结尾的最长上升子序列的长度
例:g[3]为满足最长上升子序列长度为3的序列中最小的数
对于以下序列$$1,5,3,6,7$$
$$
g[1]=1
g[2]=3 (不能是5,因为3比5小)
g[3]=6
g[4]=7
g[5]=\infty (因为不存在长度的5的最长上升子序列)
$$
同时一定满足
$$g[1]<=g[2]<=g[3]<=g[4]……..<=g[n]$$
所以为了确定序列中的一个数seq[i]的最长上升子序列长度,只需要在g数组中进行二分查找即可。查找后,查找结果即为以seq[i]结尾的最长上升子序列的长度
但要注意:
假设在g中二分查找seq[i]所得到的结果是index,那么还需要把g[index]改为seq[i],以此维护g数组的单调性(因为seq[i]一定比g[index]小,如果seq[i]比g[index]大,那么二分查找的结果就不是index了)
代码:注意，初始时g数组需要全部设置为$$\infty$$
#include
#include
#include
using namespace std;
using int_t = long long int;
int_t seq[100000 + 1];
int_t g[100000 + 1];
int_t result[100000 + 1];
int main() {
int_t n;
cin>>n;
for (int_t i = 1; i <= n; i++) cin >> seq[i];
memset(g, 0x7f, sizeof (g));
for (int_t i = 1; i <= n; i++) {
int_t index = lower_bound(g + 1, g + 1 + n, seq[i]) - g;
result[i] = index;
g[index] = seq[i];
}
int_t r = 0;
for (int_t i = 1; i <= n; i++) r = max(r, result[i]);
cout << r;
return 0;
}
因为二分查找的复杂度为$$O(log n)$$,所以该算法的复杂度为$$O(n log n)$$
两种算法的效率对比:
数据量为10000时:
每组数据第一行为算法2，第二行为算法1
1:
0
0.672
2:
0
0.656
3:
0.016
0.641
4:
0.015
0.656
5:
0.016
0.641
6:
0.015
0.719
7:
0
0.656
8:
0.016
0.609
9:
0
0.687
10:
0.016
0.672
数据量为100000时
1:
0.094
65.765
2:
0.093
63.454
3:
0.078
65.172
4:
0.093
65.391
5:
0.079
61.999
6:
0.094
63.703
7:
0.094
65.047
8:
0.094
65.124
9:
0.109
64.954
10:
0.062
63.766
可以看到,n log n的算法明显要比n^2的算法快
发表回复