#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=