最长公共上升子序列 O(n^2)

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;

int A[MAXN], B[MAXN], N, M, dp[MAXN];

int main()

{

    scanf("%d", &N);

    for(int i = 1; i <= N; i++) scanf("%d", &A[i]);

    scanf("%d", &M);

    for(int i = 1; i <= M; i++) scanf("%d", &B[i]);

    for(int i = 1; i <= N; i++)

    {

        int last = 0;

        for(int j = 1; j <= M; j++)

        {

            if(B[j] < A[i]) last = max(last, dp[j]);

            else if(B[j] == A[i]) dp[j] = last + 1;

        }

    }

    int Ans = 0;

    for(int i = 1; i <= N; i++) Ans = max(Ans, dp[i]);

    printf("%d\n", Ans);

}

其中dp[j]表示B数组恰好匹配到j位的最长长度

巴特西

最长公共上升子序列 O(n^2)

最新文章

热门文章