【38. 最长上升子序列】

• 第一类序列长度为1，没有第i - 1个数（用0表示）
• 第二类序列长度为2，倒数第二个数是整个序列的第一个数a1
• 第三类序列长度为3，倒数第二个数是a2。。。。以此类推
• 最后一个是，倒数第二个数是i - 1

• 状态表示：
  • f[i]表示从第一个数字开始算，以a[i]结尾的最大的上升序列。(以a[i]结尾的所有上升序列中属性为最大值的那一个)
• 状态计算（集合划分）：
  • 背包问题是以最后一个物品选择多少个进行分类,最长上升子序列问题因为最后一个数是i都是确定的，所以我们以第i-1个数进行分类
  • j∈(0,1,2,..,i-1), 在a[i] > a[j]时，
  • f[i] = max(f[i], f[j] + 1)。
  • 有一个边界，若前面没有比i小的，f[i]为1（自己为结尾）。
• 最后在找f[i]的最大值。
• 时间复杂度
  • O(n₂) 状态数(n) * 转移数(n)
    

注意

• 并不是每一类都存在例如a2 >= ai,此时前一个数是大于a[i]的那么a[2]不会作为序列中的数，因为是上升子序列
• 假如我们是第j类(也就是倒数第二个数是第j类)所有结尾是aj>=ai这样的子序列长度最大值（f[j] + 1）
• 最终结果ai=max(f[j]+1,aj<ai,j取指是0~i-1)

具体例子

1. 题目

2. 代码

#include <iostream>
#include <algorithm>
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;
}

3. 打印最长子序列

#include <iostream>
#include <algorithm>
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;
}

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 <iostream>
#include <algorithm>
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;
   
}

5. 总结

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

  1. 满足最优子结构

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

  2. 满足无后效性

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

  3. 设计好状态

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

  4. 设计好状态转移方程

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