481 - What Goes Up

#include<iostream>
#include<vector>
#include<cstdio>
#define MAXNEG -2134483648
using namespace std;

vector< int > Seq;
vector< int > Lis,Pre;

int LIS(int);
void PrintLIS(int n);

int main()
{
    int n,k=1,f=1;
    //freopen("in.txt","r",stdin);

    //Seq.push_back(MAXNEG);
    while(scanf("%d",&n)==1)
        Seq.push_back(n);

    n = Seq.size();
    n = LIS(n);

    printf("%d\n-\n",n);
    for (size_t i = 0; i < n; i++)
        printf("%d\n", Seq[Lis[i]]);

    return 0;
}

int LIS(int n)
{
    int u, v;
    Pre = vector< int >(n+1);
   
    Lis.push_back(0);

    for (size_t i = 1; i < n; i++)
    {
        if (Seq[Lis.back()] < Seq[i])
        {
            Pre[i] = Lis.back();
            Lis.push_back(i);
            continue;
        }
       
        for (u = 0, v = Lis.size()-1; u < v;)
        {
            int c = (u + v) / 2;
            if (Seq[Lis[c]] < Seq[i])
                u=c+1;
            else
                v=c;
        }
       

        if (Seq[i] < Seq[Lis[u]])
        {
            if (u > 0) Pre[i] = Lis[u-1];
            Lis[u] = i;
        }   
    }
   
    for (u = Lis.size(), v = Lis.back(); u--; v = Pre[v])
        Lis[u] = v;
    return Lis.size();
}