LIS & LDS

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int LIS(vector<int> A)
{
    //Longest Increasing Sequence (Not monotically!)
    int size=A.size();
    vector<int> tail(size,0);
    int len,i;
    tail[0] = A[0];
    len = 1;
    for(i=1;i<size;i++)
    {
        if(A[i]<tail[0])
            tail[0] = A[i];     // new smallest value
           
        else if( A[i] >= tail[len-1] )
            tail[len++] = A[i]; // A[i] wants to extend largest subsequence
           
        else
        {
            tail[upper_bound(tail.begin(),tail.begin()+len,A[i])-tail.begin()] = A[i];
        }
           
    }
    return len;
}

int LDS(vector<int> a)
{
    // Longest Decreasing Subsequence (Not Monotically!!)
    int size=a.size(),max=a[0],i;
    for(i=1;i<size;i++)
        if(max<a[i])max=a[i];
    max++;
    for(i=0;i<size;i++)
        a[i]=max-a[i];
    return LIS(a);
}
int main()
{
    int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
       vector<int> b(A,A+9);
    printf("Length of Lis is %d  AND LDS is %d\n",
            LIS(b),LDS(b));
    return 0;
}