vjudge链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15302

求最长上升子序列长度的问题,研究了一种o(nlongn)的算法,dp[i]表示长度为i+1的上升子序列中末尾元素的最大值。遍历一遍数组a,二分更新dp数组。

 

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

const int inf = 0x7f7f7f7f;
int a[1024], dp[1024];

int main(){
    int n; scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", a + i);
    memset(dp, inf, sizeof(dp));
    for(int i = 0; i < n; ++i)
        *lower_bound(dp, dp + n, a[i]) = a[i];
    printf("%d\n", lower_bound(dp, dp + n, inf) - dp);
    return 0;
}

 

欢迎留言