272题 最长公共上升子序列

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 3010;
int a[N], b[N], q[N][N], n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    for (int i = 1; i <= n; i++)
    {
        int maxv = 1;
        for (int j = 1; j <= n; j++)
        {
            q[i][j] = q[i - 1][j];
            if (a[i] == b[j])
            {
                //int maxv = 1;

                // for (int k = 1; k < j; k++)
                // {
                //     if (b[k] < b[j])  b[j] 就等于 a[i]，而a[i]在内层循环不变！
                //     {
                //         maxv = max(maxv, q[i - 1][k] + 1);
                //     }
                // }    初始代码有三重循环，现在将该层循环优化掉
                // 不难发现，每次j更新时，k其实不需要从1开始遍历，只需跟新的那一个j比较即可

                q[i][j] = max(q[i][j], maxv);  // 此处的maxv其实是在用前j - 1轮比较的结果！
            }
            if (b[j] < a[i])
            {
                maxv = max(maxv, q[i - 1][j] + 1); // 只比较新的j
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, q[n][i]);
    }
    cout << ans << endl;
    return 0;
}