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;
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment