【错题集-编程题】dd 爱科学 1.0（最长上升子序列 - 贪心 + 二分）

牛客对应题目链接：dd爱科学1.0 (nowcoder.com)

一、分析题目

算法思路：要想改动最小，就应该在最长非下降子序列的基础上，对不是最长的部分进行更换。

因为这道题的数据范围比较大，所以排除动态规划（N^2），应该用贪心 + 二分（N*logN）求出最长非下降子序列的长度。

当考虑一个字符能否和前面的子序列组成非递增子序列时，不需要知道它是怎样的，只需要知道它的末尾字符是什么就行。所以，只需要将长度为 x 的所有子序列中，最小的末尾存起来。

二、代码

//值得学习的代码
#include <iostream>
#include <string>

using namespace std;

const int N = 1e6 + 10;
int n;
string s;

char dp[N]; // dp[i] 表⽰：⻓度为 i 的所有的⼦序列中，最⼩的末尾是多少
int ret;

int main()
{
    cin >> n >> s;
    for(int i = 0; i < n; i++)
    {
        char ch = s[i];
        // 找出 ch 应该放在哪个位置
        if(ret == 0 || ch >= dp[ret])
        {
            dp[++ret] = ch;
        }
        else
        {
            // ⼆分出 ch 应该放的位置
            int left = 1, right = ret;
            while(left < right)
            {
                int mid = (left + right) / 2;
                if(dp[mid] > ch) right = mid;
                else left = mid + 1;
            }
            dp[left] = ch;
        }
    }
 
    cout << n - ret << endl;
 
    return 0;
}

三、反思与改进

这道题目需要着重理解 dp 的含义，可以先自己模拟一下需要存储的数据的过程。