CareerCup

How will 2 be handelled?
output can be 1,3,2,10
instead of 1,3,4,10

any will do good Tarun...it should be the max length one..bt, using the backtracking one may go back nd print all of them....

I guess it is different from LCS problem. LCS is the subsequence among 2 or more lists but in this case we have only a single list.

well lcs with same one in sorted order, find the lcs of array1 with array1 sorted...this problem is called longest increasing subsequence.....there is an standalone solution as well..with above DP:

working code in O(n2)

/* To find longest monotonically increasing subsequence */
	int a[] = { 1,4,6,2,3,0,5};
	int lcs[100], p[100];
	//initialize
	int size = sizeof(a)/sizeof(a[0]);
	for(int i=0; i < size; ++i)
	{
		lcs[i]=1;  p[i] = -1;
	}
	for(int i=0; i < size; ++i)
		for(int j=0; j < i; ++j)
		{
			if(a[i] > a[j])
			{
				//find max of lcs[i], lcs[j]+1
				if(  lcs[j]+1 > lcs[i] )
				{
					lcs[i] = lcs[j] + 1;
					p[i] = j;
				}
			}
		}
	int max=lcs[0], maxInd=0;
	for( int i=1; i < size; ++i)
		if( lcs[i] > max )
		{
			max = lcs[i];
			maxInd = i;
		}
	while( true )
	{
		cout << a[maxInd] << endl;
		maxInd = p[maxInd];
		if( maxInd == -1 )
			break;
	}

Hi,
Can you please also mention the amazon location where this question was asked?

very good site people.csail.mit.edu/bdean/6.046/dp/

O(n) Solution

public class Amazon9 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int sIndex=0;
		int eIndex=0;
		int i=0;
		int j=0;
		int [] a = {8,6,5,1,9,3,7,4,2,10};
		int max=1;
		int count=1;
		while(j<a.length)
		{
			j++;
			if(j<a.length && a[j]>=a[j-1])
			{
				count++;
			}
			else
			{
				if(count>max)
				{
					max=count;
					sIndex=i;
					eIndex=j-1;
				}
				i=j;
				count=1;
			}

		}
		System.out.println("Sequence Size:"+max);
		for(i=sIndex;i<=eIndex;i++)
			System.out.print(a[i]+",");
	}

}

Not read question properly :(

Use patience sort :
en.wikipedia.org/wiki/Patience_sorting

Nice animation at :
wordaligned.org/articles/patience-sort

@KK : I dont think that should matter. In case there are more than one options for a card to go, it should go on the pile which is the longest so far & not on the basis of the top values.

output can also be 1,3,7,10...wat about that?

int main()
{

	int a[] = { 1,4,6,2,3,0,5};
	int lcs[100], p[100];
	int i=0,j=0, maxIndex=0;
	//initialize
	int size = sizeof(a)/sizeof(a[0]);
	for(i=0; i < size; ++i)
	{
		lcs[i]=1;  p[i] = -1;
	}
	
	for(i=1; i< size; i++ )
	{
		for(j = i-1; j>=0; j-- )
		{
			if( (a[j] < a[i] ) && (lcs[i] < (lcs[j] + 1)))
			{
				lcs[i] = lcs[j]+1;
				p[i]  = j;
				if( lcs[maxIndex] < lcs[i] )
					maxIndex = i;
			}
		}
	}
	i = maxIndex;
	do
	{
		cout<<a[i]<<",";
		i = p[i];		
	}while(i!=-1);

	return 0;
}

Time complexity O(n2)

We can use a stack. Push first number and check for larger number with top. When you see a small number than top the pop the top and push the number to stck. If the number is larger than top then push that number..

It is Longest Common Subsequence Problem(LCS). It is easy to find an O(n^2) solution for this one. Use the following DP:
L(i) = max(L(j))+1 if a(j) <= a(i) for all j<i
else L(i) = max(L(j)) if a(j) > a(i)

Write a DP for the same computing bottom to top and get the soln....