Friday, February 22, 2013

longest increasing subsequence


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

void LongestSubSequence(vector<int> X)
{
int n=X.size();
vector<int> M(n+1);
int L=0;
for(int i=0;i<n;i++)
{
int j;
if(L==0)j=0;
else
{
for(j=1;j<=L;j++)
{
if(X[M[j]]>X[i])
break;
}
j--;
}
if(j==L || X[i]<X[M[j+1]])
{
M[j+1]=i;
L=max(L,j+1);
}
}
cout<<L<<endl;
}

No comments:

Post a Comment