272. 最长公共上升子序列

题目来源

acwing

题目难度

3星

算法标签

dp + 优化

参考程序

#include <iostream>

using namespace std;

const int N = 3005;

int n;

int a[N], b[N];

//dp[i][j]表示a的前i个数，b的
//前j个数,并且以b[j]结尾,的最长
//公共上升子序列长度
int dp[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 ++)
        {
            //不包括a[i]
            dp[i][j] = dp[i-1][j];
            //包含a[i]
            if(a[i] == b[j])
            {
                dp[i][j] = max(dp[i][j], maxv);
            }
            //更新maxv:在b[1~j-1]中小于a[i]的所有数的dp[i-1][k]+1的max
            if(b[j] < a[i])
            {
                maxv = max(maxv, dp[i-1][j]+1);
            }
        }
    }
    int ans = 0;
    for(int j = 1; j <= n; j ++)
    {
        ans = max(ans, dp[n][j]);
    }
    cout << ans << endl;
}