Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //longest increasing subsequence
- //nasarouf@cs.ubc.ca
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement