Aug 11, 2009

Longest increasing subsequence in array A[n]

Longest increasing subsequence in array A[n]
L(j)=max{L(i)}+1, where i < j and A[i] < A[j]
max_g=max{L(j)}
O(n^2)

int foo(int A[], int len)
{
int max_g=0;
int L[len];
for(int j=0;j < len;j++)
{
for(i=0; i < j; i++)
{
if(A[i] < A[j])
L[j]=max(L[j],L[i]+1);
}
max_g=max(max_g,L[j]);
}
return max_g;
}

No comments:

Post a Comment