定义
在一个序列中最长的单调递增的子序列，称为最长上升子序列(Longest
Increasing Subsequence)。
求解算法
\(O(n^2)\)算法
思路
设\(a[1\ldots
n]\)表示原序列，\(f[i]\)表示以第\(i\)个数结尾的LIS长度。 状态转移方程：
\[f[i]=max\{f[j]+1\},\quad j< i,\quad a[j]< a[i]\]
答案为\(max\{f[i]\},\quad 1\leq i \leq n\)。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=200005;
int n,a[MAXN],f[MAXN],ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
f[i]=1;
}
for(int i=2;i<=n;++i)
for(int j=1;j<i;++j)
if(a[i]>a[j]&&f[j]+1>=f[i])f[i]=f[j]+1;
for(int i=1;i<=n;++i)ans=max(ans,f[i]);
printf("%d",ans);
return 0;
}
|
\(O(n\log n)\)算法
思路
设\(a[1\ldots
n]\)表示原序列，\(f[i]\)表示长度为\(i\)的上升子序列的最小末尾，\(len\)表示当前LIS长度，可得\(f\)为递增数列。
每次读入一个数字\(k\)，先与\(f[len]\)比较，如果大于则添加至\(f[++len]\)，作为原来\(f[len]\)的后继。
否则在\(f\)中二分查找，找到\(f[i]< k\leq
f[i+1]\)，更新为\(f[i+1]\)为\(k\)，即\(k\)比原来\(f[i+1]\)更优，可作为\(f[i]\)的后继。
答案为\(len\)。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=200005;
int n,s[MAXN],f[MAXN],len;
int main()
{
scanf("%d",&n);
scanf("%d",&s[1]);
f[1]=s[1];
len=1;
for(int i=2;i<=n;++i)
{
scanf("%d",&s[i]);
if(s[i]>f[len])f[++len]=s[i];
else
{
int l=1,r=len;
while(l<r)
{
int mid=(l+r)>>1;
if(s[i]>f[mid])l=mid+1;
else r=mid;
}
f[l]=s[i];
}
}
printf("%d\n",len);
return 0;
}
|