In O(n^2)
eg.
#include<stdio.h>
#include<conio.h>
using namespace std;
int a[]={9,8,10,15,6,22,23,4,111,112};
int p[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int m[10];
int main()
{
int max, pos, i,j;
for(i=9; i>=0; i--)
{
for(j=i+1; j<10; j++)
{
if(a[i]<a[j] && m[i]<1+m[j])
{
m[i]=1+m[j];
p[i]=j;
}
}
}
max=m[0];
pos=0;
for(i=1; i<10; i++)
{
if(max<m[i])
{
max=m[i];
pos=i;
}
}
printf(" %d", a[pos]);
while(p[pos]!=-1)
{
printf(" %d", a[p[pos]]);
pos=p[pos];
}
getch();
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
