【38. 最长上升子序列】

具体例子

1. 题目

2. 代码

#include 
#include 
using namespace std;
const int N = 1010;
int n;
int a[N], f[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)   cin >> a[i];
    
    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1;   //当长度为1的时候只有a[i]一个数(  // 设f[i]默认为1，找不到前面数字小于自己的时候就为1)
        for (int j = 1; j < i; j ++)
        {
            if (a[j] < a[i])
            {
                f[i] = max(f[i], f[j] + 1); // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
            }
        }
        
    }
    int res = 0;  
    //目前f[i]中存的都是最大值，需要从这些最大值中在找到一个最大值
    //f[1],f[2],f[3].....f[i]，这些数都是经过上面计算得到的最大值，需要把这些书在进行比较获得最大值
    for (int i =1; i <= n; i ++)  res = max(res, f[i]);
    
    cout << res;
    return 0;
}
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

3. 打印最长子序列

#include 
#include 
using namespace std;

const int N = 1010;
int n;
int f[N], a[N],g[N]; //g[N]存储每一个转移是怎么转移过来的(存储下标值)
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    
    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        g[i] = 0;   //表示只有一个数
        for (int j = 1; j < i; j ++)
        {
            if (a[j] < a[i])
                //f[i] = max(f[i], f[j] + 1);
                if (f[i] < f[j] + 1)
                {
                    f[i] = f[j] + 1;  //更新f[i]
                    g[i] = j;  //记录f[i]是从哪个状态转移过来的
                }
        }
    }
    
    //int res = 0;
    int k = 1;  //记录最优解的下标
    
    for (int i = 1; i <= n; i ++) 
    {
       // res = max(res, f[i]);
       if (f[k] < f[i])
          k = i;
    }
    
    cout << f[k] << endl;  //最大值
    
    //倒序推出序列，根据g[]数组可以知道f[i]是从哪个状态转移过来的
    for (int i = 0, len = f[k]; i < len; i ++)
    {
        cout <<' '<<a[k];   //f[k]表示以k结尾的最长序列，可以先输出a[k]
        //printf("%d ", a[k]);
        k = g[k];  //是从g[k]转移过来的
    }  
    
    return 0;
}
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

4. 优化

• 基于单调性：找到一个最大的小于等于当前数的数, 我们可以用 二分 来优化
• 二分的思路：
  1. 先定义边界，l = 0, r = len, 其中len是q数组的长度
  2. 然后确定check函数, 可以先找到不等式中c < x ≤ a ≤ b的c
     • 通过q[r + 1] = a[i]来将x覆盖a的值
     • 同时也要考虑, 需要扩大q数组的长度
       • 即r + 1 > len时, 表示超出了二分边界，这时就要len ++更新q的长度

时间复杂度

• 遍历每个数是 O(n)O(n)
• 遍历q数组每个数, 找到一个最大的小于当前数x的数c O(logn)O(logn)
• 因此时间复杂度是 O(nlogn)

#include 
#include 
using namespace std;

const int N = 100010;
int n;
int q[N], a[N];  //a[N]存储每个数，q[N]存储不同长度下，所有不同长度的上升子序列末尾元素最小的数

int main()
{
   cin >> n;
   for (int i = 0; i < n; i ++)  cin >> a[i];
   
   int len = 0;   //存储当前最大长度，存储q里面的元素个数
   
   q[0] = -2e9;    //小于某个数的一定存在，将q[0]设置为哨兵
   //这里e要二分出来，小于某个数的最大的数（这道题是小于a[i]的最大的数）
   for (int i = 0; i < n; i ++)
   {
       int l = 0, r = len;
       while (l < r)
       {
           int mid = l + r + 1 >> 1;
           if (q[mid] < a[i]) l = mid;
           else r = mid - 1;
        
       }
       len = max(len, r + 1);  //将长度更新为最大值，r是可以接在某个数的后面，接完之后长度+1；
        q[r + 1] = a[i];     //r是小于a[i]的最后一个数，所以r + 1大于等于a[i]，要替换成更小的
   }
   cout << 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
32
33

5. 总结

• 哪些题目适合用DP算法解决?如何设计好DP算法:

  1. 满足最优子结构

     • 大问题可以由小问题推出，大问题与小问题求解思路一致。

  2. 满足无后效性

     • 一旦f(n)确定，后续我们直接调用它的值就可以，而不用关心它是怎样过来的

  3. 设计好状态

     • 想办法把当前局面给表达出来

  4. 设计好状态转移方程

     • 可以从两个方面考虑，我从哪里来，或者我到哪里去