最长上升子序列

描述

一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出

最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8
样例输出

一、确定状态

我们让dp[k] 代表从 1->k 的最长上升子序列的长度。状态有N个

二、确定转移方程

让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。

　　前1个数 d(1)=1 子序列为2；

　　前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7

　　前3个数在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1

　　前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5

　　前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6

　　前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4

　　前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3

　　前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8

　　前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9

　　d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5

　　总结一下，d(i)就是找以A[i]结尾的，在A[i]之前的最长上升子序列+1，当A[i]之前没有比A[i]更小的数时，d(i)=1。所有的d(i)里面最大的那个就是最长上升子序列

想要求得最长上升子序列的长度，来源只有一种——前一个最长上升子序列的长度+1 ，据此就得到了状态转移方程。

时间复杂度：O (n^2)

Code：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <stdlib.h>
 5 #include <string>
 6 #include <string.h>
 7 #include <set>
 8 #include <queue>
 9 #include <math.h>
10 #include <stdbool.h>
11 
12 #define ll long long
13 #define inf 0x3f3f3f3f
14 using namespace std;
15 const int MAXN = 1005;
16 
17 int dp[MAXN];
18 int a[MAXN];
19 int N;
20 
21 
22 int main()
23 {
24     scanf("%d",&N);
25     for (int i=1;i<=N;i++)
26         cin >> a[i];
27     for(int i=1;i<=N;i++)
28         dp[i] = 1;
29     for (int i=2;i<=N;i++)
30     {
31         for (int j=1;j<i;j++)
32         {
33             if (a[j]<a[i])
34                 dp[i]=max(dp[j]+1,dp[i]);
35         }
36     }
37     sort(dp+1,dp+1+N);
38     cout << dp[N] << endl;
39     return 0;
40 
41 }

那么如果我们想输出这个最长上升子序列呢？

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <stdlib.h>
 5 #include <string>
 6 #include <string.h>
 7 #include <set>
 8 #include <queue>
 9 #include <math.h>
10 #include <stdbool.h>
11 
12 #define ll long long
13 #define inf 0x3f3f3f3f
14 using namespace std;
15 const int MAXN = 1005;
16 
17 int dp[MAXN];
18 int a[MAXN];
19 int N;
20 
21 
22 int main()
23 {
24     freopen("../in.txt","r",stdin);
25     int pre[MAXN];
26     memset(pre,0, sizeof(pre));
27     scanf("%d",&N);
28     for (int i=1;i<=N;i++)
29         cin >> a[i];
30     for(int i=1;i<=N;i++)
31         dp[i] = 1;
32     for (int i=1;i<=N;i++)
33     {
34         for (int j=1;j<i;j++)
35         {
36             if (a[j]<a[i])
37             {
38                 dp[i] = max(dp[j] + 1, dp[i]);
39             }
40         }
41     }
42     int maxn = 0;
43     for (int i=1;i<=N;i++)
44     {
45         if (dp[i]>maxn)
46         {
47             maxn = dp[i];
48         }
49     }
50     int ans[100];
51     for (int i=1;i<=maxn;i++)
52     {
53         for (int j=1;j<=N;j++)
54         {
55             if (dp[j] == i)
56                 ans[i] = a[j];
57         }
58     }
59     for (int i=1;i<=maxn;i++)
60         printf("%d ",ans[i]);
61     return 0;
62 
63 }

优化算法：贪心+二分

新建一个 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(n^2)。我们注意到 low 数组内部一定是单调不降的，所有我们可以二分 low 数组，找出第一个大于等于a[ i ]的元素。二分一次 low 数组的时间复杂度的O(lgn)，所以总的时间复杂度是O(nlogn)。

Code：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <stdlib.h>
 5 #include <string>
 6 #include <string.h>
 7 #include <set>
 8 #include <queue>
 9 #include <math.h>
10 #include <stdbool.h>
11 
12 #define ll long long
13 #define inf 0x3f3f3f3f
14 using namespace std;
15 const int MAXN = 1005;
16 
17 int dp[MAXN];
18 int a[MAXN];
19 int N;
20 
21 
22 int main()
23 {
24     scanf("%d",&N);
25     for (int i=1;i<=N;i++)
26         cin >> a[i];
27     memset(dp,inf, sizeof(dp));
28     dp[1] = a[1];
29     int len = 1;
30     int pos;
31     for (int i=1;i<=N;i++)
32     {
33         if (a[i]<=dp[len])
34         {
35             pos=lower_bound(dp+1,dp+len+1,a[i])-dp;
36             dp[pos] = a[i];
37         }
38         else
39         {
40             len++;
41             dp[len] = a[i];
42         }
43     }
44     cout << len << endl;
45     return 0;
46 
47 }

这里再讲一个最长上升子序列的变种题目：

求最长上升子序列的个数

这一个算法思想上和求最长子序列是差不多的，唯一难的地方在于如何去记录不同的序列

对于最长子序列的个数，需要我们在处理dp的时候来记录，我们设count[i]为以第i个数结尾的最长序列的个数，与dp同理，count初值也都是1；

状态转移的时候，如果dp更新了，也就是说（dp[j]+1>dp[i]）说明这个长度的序列是新出现的，我们需要将count[i]设置为count[j]，因为新序列中，最新的数提供了序列的尾巴，数量是由前面积累的（或者说转移）

举例序列[1 1 3 7]我们易得数字3对应的dp=2,count=2,因为可以构成两个[1 3]那么我们操作到数字7的时候，发现接在3后面最长，就可以转移count来作为初始数量；

当dp[j]+1==dp[i]的时候，如同样例，操作7的时候，我们最先发现了可以接在5后面，最长序列[1 3 5 7],然后发现可以接在4后面，[1 3 4 7]，长度也是4，这时候就同样需要转移count，加上去 count[i]+=count[j]

最后我们需要遍历dp，找到dp[i]=我们记录的最大值的时候，累加我们得到的count[i]，即为所求结果，时间复杂度是O(n^2)

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <stdlib.h>
 5 #include <string>
 6 #include <string.h>
 7 #include <set>
 8 #include <queue>
 9 #include <math.h>
10 #include <stdbool.h>
11 
12 #define ll long long
13 #define inf 0x3f3f3f3f
14 using namespace std;
15 const int MAXN = 1005;
16 
17 int dp[MAXN];
18 int a[MAXN];
19 int cnt[MAXN];
20 int N;
21 
22 
23 int main()
24 {
25     scanf("%d",&N);
26     for (int i=1;i<=N;i++)
27         cin >> a[i];
28     for (int i=1;i<=N;i++)
29     {
30         dp[i] = 1;
31         cnt[i] = 1;
32     }
33     int mxn = 0;
34     for (int i=1;i<=N;i++)
35     {
36         for (int j=1;j<i;j++)
37         {
38             if (a[j] < a[i])
39             {
40                 if (dp[j]+1 > dp[i])
41                 {
42                     dp[i] = dp[j] + 1;
43                     cnt[i] = cnt[j];
44                 }
45                 else if (dp[j] + 1 == dp[i])
46                 {
47                     cnt[i] += cnt[j];
48                 }
49             }
50         }
51         mxn = max(mxn,dp[i]);
52     }
53     cout << mxn << endl;
54     int res = 0;
55     for (int i=1;i<=N;i++)
56     {
57         if (dp[i] == mxn)
58         {
59             res+= cnt[i];
60         }
61     }
62     cout << res << endl;
63     return 0;
64 }