O（mn）实现LCIS

程序员旭露技术 2022年11月9日

0 收藏 612 点赞 5,141 浏览 1150 个字

序：
LCIS即求两序列的最长公共不下降子序列。思路于LCS基本一致。

用dp[i][j]记录当前最大值。

代码实现：

/*
About: LCIS O(mn)
Auther: kongse_qi
Date:2017/04/26
*/
#include <bits/stdc++.h>
#define maxn 505
using namespace std;int n, m, a[maxn], b[maxn];void Init()
{
    scanf("%d%d", &n， &m);
    for(unsigned i = 0; i != n; ++i)
    {
        scanf("%d", &a[i]);
    }
    for(unsigned i = 0; i != m; ++i)
    {
        scanf("%d", &b[i]);
    }
    return ;
}int Lcis()
{
    int maxx, dp[maxn][maxn], ans = 0;
    for(unsigned i = 1; i != n+1; ++i)
    {
        maxx = 0;
        for(unsigned j = 0; j != m; ++j)
        {
            dp[i][j] = dp[i-1][j];
            if(a[i-1] > b[j])
            {
                maxx = max(dp[i-1][j], maxx);
            }
            if(a[i-1] == b[j])
            {
                dp[i][j] = maxx+1;
                maxx = max(maxx, dp[i-1][j]);
            }
        }
    }
    for(unsigned i = 0; i != m; ++i)
    {
        ans = max(ans, dp[n][i]);
    }
    return ans;
}int main()
{
    //freopen("test.in", "r", stdin);    Init();
    cout << Lcis();
    return 0;
}

空间也是O（n^2），仔细阅读则会发现依然可以滚动数组，是空间复杂度降到O（n）。
与LCS的方式完全一致。

int Lcis()
{
    int maxx, dp[2][maxn], ans = 0;
    memset(dp, 0, sizeof dp);
    for(unsigned i = 1; i != n+1; ++i)
    {
        maxx = 0;
        for(unsigned j = 0; j != m; ++j)
        {
            dp[i&1][j] = dp[(i&1)^1][j];
            if(a[i-1] > b[j])
            {
                maxx = max(dp[(i&1)^1][j], maxx);
            }
            if(a[i-1] == b[j])
            {
                dp[i&1][j] = maxx+1;
                maxx = max(maxx, dp[(i&1)^1][j]);
            }
        }
    }
    for(unsigned i = 0; i != m; ++i)
    {
        ans = max(ans, dp[n&1][i]);
    }
    return ans;
}