CareerCup

Let A be the original array. Steps are as below:
- Let B=A sorted in increasing order.
- Output the "Longest Common Subsequence" of B from A

@cobra :
picked up this example from wiki .google both terms longest increasing subarray. longest increasing subsequence to understand better.

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, …
a longest increasing subsequence is
0, 2, 6, 9, 13, 15.

this can be done by DP, try using LIS[i]=1+max{LIS[1.....i-1]}... i hv nt included the base cases here...

#include<iostream>

nb

#include<iostream>
using namespace std;
int main()
{

int a[] = {5,4,10,11,9,13,14,15,8,6};

int count =1, max=1;

for(int i=0; i<10; i++)
{ if(a[i+1]>a[i])
count++;
else
{if(count >= max)
{max=count;
count =1;
}
}
}

cout<<max;
return 0;

}

public class LongestIncreasingSubsequence {

	    /**
	     * Returns index in T for ceiling of s
	     */
	    private int ceilIndex(int input[], int T[], int end, int s){
	        int start = 0;
	        int middle;
	        int len = end;
	        while(start <= end){
	            middle = (start + end)/2;
	            if(middle < len && input[T[middle]] < s && s <= input[T[middle+1]]){
	                return middle+1;
	            }else if(input[T[middle]] < s){
	                start = middle+1;
	            }else{
	                end = middle-1;
	            }
	        }
	        return -1;
	    }
	    
	    public int longestIncreasingSubSequence(int input[]){
	    	if(input==null || input.length==0)
	    		return 0;
	        int T[] = new int[input.length];//temporary array to hold the minimum element of length i+1, scanned so far 
	        int R[] = new int[input.length]; // result array, to traverse the longest subsequence
	        for(int i=0; i < R.length ; i++) {
	            R[i] = -1;
	        }
	        T[0] = 0;// longest subsequence of length 1, will start at index 0 (Initialization).
	        int len = 0; // longest subsequence length
	        for(int i=1; i < input.length; i++){
	            if(input[T[0]] > input[i]){ //if input[i] is less than 0th value of T then replace it there.
	                T[0] = i;
	            }else if(input[T[len]] < input[i]){ //if input[i] is greater than last value of T then append it in T
	                len++;
	                T[len] = i;
	                R[T[len]] = T[len-1];
	            }else{ //do a binary search to find ceiling of input[i] and put it there.
	                int index = ceilIndex(input, T, len,input[i]);
	                T[index] = i;
	                R[T[index]] = T[index-1];
	            }
	        }
	        
	        System.out.println("R: ");
	        for(int i: R)
	        	System.out.print(i+  "  " );
	        System.out.println();
	        System.out.println("T: ");
	        for(int i: T)
	        	System.out.print(i+  "  " );
	        System.out.println();
	        

	        //this prints increasing subsequence in reverse order.
	        System.out.print("Longest increasing subsequence ");
	        int index = T[len];
	        while(index != -1) {
	            System.out.print(input[index] + " ");
	            index = R[index];
	        }

	        System.out.println();
	        return len+1;
	    }
	    
	    public static void main(String args[]){
	        //int input[] = {2,5,3,1,2,10,6,7,8};
	        int input[] = {3, 4, -1, 5, 8, 2, 3, 12, 7, 9, 10};
	        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
	        System.out.println("Maximum length " + lis.longestIncreasingSubSequence(input));
	    }

}

mentioning Kadane's algorithm on the interview would be enough I guess. It is a known proved algorithms for such kind of DP problems.

in can be done in O(n)..

keep a counter.. increment the counter while traversing the increasing array elements..

when a small element is encountered...

max_count = count;
count = 0;

and then resume traversing keep on incrementing the count till next small element is encountered..

if(count>max_count)  
 max_count = count;

and also keep track of the start index and end index of the subsequence to print the elements