LIS (longest increasing subsequence)

//longest increasing subsequence
//[email protected]

int LISlast[MAX+1];
//increasing
int LIS(int *x, int n){
    int l=0,*p;
    LISlast[0]=-1;
    for (int i=0; i<n; i++){
        p=lower_bound(LISlast,LISlast+l+1,x[i]);
        if (p==LISlast+l+1) ++l;  //get rid of the +1 ???
        *p=x[i];
    }
    return l;
}
//non-decreasing
int LNDS(int *x, int n){
    int l=0,*p;
    LISlast[0]=-1;
    for (int i=0; i<n; i++){
        p=upper_bound(LISlast,LISlast+l,x[i]);
        if (p==LISlast+l) ++l;
        *p=x[i];
    }
    return l;
}