最长递增子序列

题目描述

给定一个序列 An = a1 ,a2 ,  ... , an ，找出最长的子序列使得对所有 i < j ，ai < aj 。求出这个子序列的长度

输入描述:

输入的序列

输出描述:

最长递增子序列的长度

示例1

输入

复制

1 -1 2 -2 3 -3 4

输出

复制

4

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INT_MAX = 1e5+5;
int Input[INT_MAX];
int DP[INT_MAX];
int Index = 0;

int main(){
    while(scanf("%d",&Input[Index]) != EOF){
        Index++;
    }
    for(int i = 0;i < Index;i ++){
        DP[i] = INT_MAX;
    }
    for(int i = 0;i < Index;i ++){
        *lower_bound(DP,DP + Index,Input[i]) = Input[i];
    }
    auto it = lower_bound(DP,DP + Index,INT_MAX);
    cout << it - DP << endl;
    return 0;
}