最长上升子序列

模版

LIS1

复杂度:O(n^2)

a[]下标为1~ndp[]表示以该点结束的最长上升子序列的长度

int dp[1050]={},cnt;
int LIS(int *a,int n){
    cnt = 0;
    for (int i=1; i<=n; i++) {
        dp[i]=1;
        for (int j=1; j<i; i++)
            if (a[j]<a[i])
                dp[i]=max(dp[i],dp[j]+1);
        cnt=max(cnt,dp[i]);
    }
    return cnt;
}

LIS2

复杂度:O(nlogn)

a[]下标为1~ndp[]并不会存储最长上升子序列,只是长度相等

const int maxn = 1005;
int dp[maxn];
int LIS(int a[], int n) {
    int len = 1;
    dp[1] = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i]>dp[len]) {
            dp[++len]=a[i];
        }
        else{
            int pos = lower_bound(dp + 1, dp + len + 1, a[i]) - dp; //找到插入位置
            dp[pos] = a[i];
        }
    }
    return len;
}

results matching ""

    No results matching ""