最长上升子序列(严格递增)

int dp[MAXN];
int LIS(vector<int>&a){
    memset(dp, 0x3f, sizeof(int)*a.size());
    int len = 1;
    dp[0] = a[0];
    for (int i = 1; i < a.size(); ++i)    {
        int pos = lower_bound(dp, dp + len, a[i]) - dp;
        dp[pos] = a[i];
        len = max(len, pos + 1);
    }
    return len;
}

标签: none

添加新评论