#include<stdio.h>
#include<string.h>
void lis(int str[],int n)
{
int len[n],prev[n],i,j,max=-1,k,b[n],a=0;
for(i=0;i<n;i++){
len[i]=1;
prev[i]=-1;
}
for(i=1;i<n;i++)
for(j=0;j<i;j++){
if(str[i]>str[j]&& len[i]<(len[j]+1)){
len[i]=len[j]+1;
prev[i]=j;
}
}
for(i=0;i<n;i++)
if(len[i]>max)
{ max=len[i]; k=i;}
b[a]=str[k];
for(i=prev[k];i>=0;i=prev[k])
{b[++a]=str[i];k=i;}
for(i=max-1;i>=0;i--)
printf("%d ",b[i]);
}
main()
{
int str[]={5,9,4};
lis(str,sizeof(str)/4);
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RyaW5nLmg+CnZvaWQgbGlzKGludCBzdHJbXSxpbnQgbikKewoJaW50IGxlbltuXSxwcmV2W25dLGksaixtYXg9LTEsayxiW25dLGE9MDsKCWZvcihpPTA7aTxuO2krKyl7CgkJbGVuW2ldPTE7CgkJcHJldltpXT0tMTsKCX0KCWZvcihpPTE7aTxuO2krKykKCWZvcihqPTA7ajxpO2orKyl7CgkJaWYoc3RyW2ldPnN0cltqXSYmIGxlbltpXTwobGVuW2pdKzEpKXsKCQkJbGVuW2ldPWxlbltqXSsxOwoJCQlwcmV2W2ldPWo7CgkJCQoJCX0KCX0KCWZvcihpPTA7aTxuO2krKykKCQlpZihsZW5baV0+bWF4KQoJCXsJbWF4PWxlbltpXTsgaz1pO30KCWJbYV09c3RyW2tdOwoJZm9yKGk9cHJldltrXTtpPj0wO2k9cHJldltrXSkKCQl7YlsrK2FdPXN0cltpXTtrPWk7fQoJZm9yKGk9bWF4LTE7aT49MDtpLS0pCgkJcHJpbnRmKCIlZCAiLGJbaV0pOwp9Cm1haW4oKQp7CiAgICBpbnQgc3RyW109ezUsOSw0fTsKICAgIGxpcyhzdHIsc2l6ZW9mKHN0cikvNCk7CiAgICByZXR1cm4gMDsKfQo=