常规方法
很容易想到它的转移方程f[i]=max（f[j]）+1（要求a[i]>a[j] or a[i]<a[j]）
这样一种O(n2)的方法，很容易理解。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int LDS(int n)
{
int res = 0;
for(int i = 0; i < n; ++i) {
dp[i] = 1;
for(int j = 0; j < i; ++j) {
if(arr[i] < arr[j]) dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
return res;
}
|
二分查找优化
我们可以维护一个数组d来实现O(nlogn)的算法。
定义：a[1..n]为原始序列，d[k]表示长度为k的不下降子序列末尾元素的最小值，len表示当前已知的最长子序列的长度。
初始化：$d[1]=a[1]; len=1; $
新建一个low数组，low[i]表示长度为i的LIS结尾元素的最小值。对于一个子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护low数组。
对于每一个a[i]，如果a[i]>low[当前最长的LIS长度]，就把a[i]接到当前最长的LIS后面， 即：low[++当前最长的LIS长度]=a[i]。
那么，怎么维护low数组呢？
对于每一个a[i]，如果a[i]能接到LIS后面，就接上去；否则，就用a[i]取更新low数组。
具体方法是:在low数组中找到第一个大于等于a[i]的元素low[j]，用a[i]去更新low[j]。如果从头到尾扫一遍low数组的话，时间复杂度仍是O(n2)。我们注意到low数组内部一定是单调不降的，所有我们可以二分查找的方式，找出第一个大于等于a[i]的元素。二分一次low数组的时间复杂度的O(lgn)，所以总的时间复杂度是O(nlogn)。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5;
int arr[MAXN + 5];
int d[MAXN + 5];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; ++i) cin >> arr[i];
d[0] = arr[0];
int len = 1;
for(int i = 1; i < n; ++i) {
if(arr[i] > d[len - 1]) d[len++] = arr[i];
else {
int index = upper_bound(d, d + len, arr[i]) - d;
d[index] = arr[i];
}
}
cout << len << endl;
return 0;
}
|
最长下降子序列写法：
按照上面最长上升子序列的写法，我们把if语句的大于号改变即可，然后，因为upper_bound函数查找的是从大到小排好的d数组，所以我们需要添加一个比较规则。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5;
int arr[MAXN + 5];
int d[MAXN + 5];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; ++i) cin >> arr[i];
d[0] = arr[0];
int len = 1;
for(int i = 1; i < n; ++i) {
if(arr[i] < d[len - 1]) d[len++] = arr[i];
else {
int index = upper_bound(d, d + len, arr[i], greater<int>()) - d;
d[index] = arr[i];
}
}
cout << len << endl;
return 0;
}
|
当然，如果要求最长不下降或者最长不上升子序列的话，改一下判断条件，增加一个等于号即可。
树状数组优化
我们再来回顾O(n2)的状态转移方程：$F[i]=max {F[j]+1 }(1<=j< i,A[j]< A[i]) $
我们在递推F数组的时候，每次都要把F数组扫一遍求F[j]的最大值，时间开销比较大。我们可以借助数据结构来优化这个过程。用树状数组来维护F数组（分块也是可以的，但是分块是O(n*sqrt(n)）的时间复杂度，不如树状数组跑得快），首先把A数组从小到大排序，同时把A[i]在排序之前的序号记录下来。然后从小到大枚举A[i]，每次用编号小于等于A[i]编号的元素的LIS长度+1来更新答案，同时把编号小于等于A[i]编号元素的LIS长度+1。因为A数组已经是有序的，所以可以直接更新。
另外，去重和排序可以一步进行，使用c++的map可以对其速度做进一步优化。
如果求最长下降子序列，排序规则改为非升序即可，如果求最长不上升或最长不下降子序列，则不用去重。
代码实现：
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
#define lowbit(x) ((x) & (-x))
using namespace std;
typedef long long ll;
const int MAXN = 1e3;
struct node {
int val, id;
inline bool operator < (const node &x) const {
return val < x.val;
}
inline bool operator == (const node &x) const {
return val == x.val;
}
}arr[MAXN + 5];
int n, T[MAXN + 5];
void update(int x, int y)
{
for(int i = x; i <= n; i += lowbit(i))
T[i] = max(T[i], y);
}
int query(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i))
res = max(res, T[i]);
return res;
}
int main()
{
while(cin >> n) {
for(int i = 1; i <= n; ++i) {
cin >> arr[i].val;
arr[i].id = i;
}
sort(arr + 1, arr + n + 1);
int ans = 0;
n = unique(arr + 1, arr + 1 + n) - 1 - arr;
for(int i = 1; i <= n; ++i) cout << arr[i].val << " " << arr[i].id << endl;
for(int i = 1; i <= n; ++i) {
int maxv = query(arr[i].id);
update(arr[i].id, maxv + 1);
ans = max(ans, maxv + 1);
}
cout << ans << endl;
}
return 0;
}
|
