最长上升子序列, 百练(Bailian)2757

百练2757

最基础的最长上升子序列 ; n2 的复杂度的实现和 nlogn 的复杂度的实现 ;

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

const int maxn = 1005;
const int INF = 0x3f3f3f3f;
int dp[maxn], a[maxn];

// n2复杂度的实现;
// dp[i]表示以a[i]为结尾的, 最长上升子序列的长度;
// 
int dp_n2(int n){
    memset(dp ,0, sizeof(dp));
    int ans = 0;
    for(int i=0;i<n;i++){
        dp[i] = 1;
        for(int j=0;j<i;j++){
            if(a[j] < a[i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

// nlogn复杂度的实现;
// dp[i]表示长度为 i+1 的上升子序列中末尾元素的最小值;
// 利用二分搜索实现 nlogn 的复杂度
// 
int dp_nlogn(int n){
    memset(dp, 0x3f, sizeof(dp));
    int ans = 0;
    for(int i=0;i<n;i++){
        *lower_bound(dp, dp + n, a[i]) = a[i];
    }
    return lower_bound(dp, dp + n, INF) - dp;
}

int main(){
    int n, ans = 0;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
    }

    printf("%d\n", dp_n2(n));
    printf("%d\n", dp_nlogn(n));
    return 0;
}