CareerCup

Sort the vector first, and then looking fo the longest subsequence?
The solution works, but not the one that interviwer expects...

suppose length[i] is the length of the longest increasing subsequence ending at index i.

length[0] = 1
for all index from 1 to n-1
if array[i] > array[i-1] then length[i] = length[i-1]+1 because we are extending the sequence ended at index (i-1) by 1
else length[i] = 1 because we are starting new sequence from ith index.

find greatest length[i] for all i and is the answer required. similarly can be done for decreasing subsequence. time O(n)

public static void findArray(int[] array){

int maxStartingPos = -1;
int tempMaxStartingPos = -1;
int maxLength = -1;
int tempMaxLength = -1;

for(int i = 0; i < array.length-1; i++){
int fist = array[i];
int second = array[i+1];
if(fist<=second){
if( (tempMaxStartingPos+tempMaxLength)==i){
tempMaxLength++;
}else{
tempMaxStartingPos = i;
tempMaxLength = 1;
}
}else{
if(maxLength<tempMaxLength){
maxLength=tempMaxLength;
maxStartingPos = tempMaxStartingPos;
}
}
}

System.out.println("Max Elements");
for(int i = maxStartingPos; i<=maxStartingPos+maxLength;i++){
System.out.print(array[i]);
}
}

This works for ascending

void findSubsequence(int [] A, int n)
{
// A is the input array
// n is the size of array
int maxAsc = 0;
int maxDsc = 0;
int indexAsc = 0;
int indexDsc = 0
int maxLenAsc = 0;
int maxLenDsc = 0;

if (n == 0) std::cout<<"empty";
if(n == 1) std::cout<< A[0];

for(int i = 1; i < n ; i++)
{
if(A[i] < A[i-1])
{
max = A[i];
maxDsc++;
if (maxLenDsc < maxDsc)
{
indexDsc = i;
}

}
else
{
maxLenDsc = maxDsc;
maxDsc = 0;
}
if(A[i] > A[i-1])
{
max = A[i];
maxAsc++;
if (maxLenAsc < maxAsc)
{
maxLenAsc = maxAsc;
indexAsc = i;

}

}
else
{
maxAsc = 0;
}
}
if (maxLenAsc > maxLenDsc)
{
for(int i = (indexAsc - maxLenAsc); i < indexAsc ; i ++)
{
std::cout<<A[i];
}
else
{
for(int i = (indexDsc - maxLenDsc); i < indexDsc ; i ++)
{
std::cout<<A[i];
}
}
}
}

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int main(){
	vector<int> numbers;
	int n, num, i;
	int start_index, end_index, max = 0, count = 0;
	
	//User Input
	cin>>n;
	for( i = 0 ; i<n ; i++) {
		cin>>num;
		numbers.push_back(num);
	}

	//--------For Ascending---------------------------------------------------------------------------
	for( i = 0 ; i<n ; i++){
		if(numbers[i] == numbers[i - 1] + 1){
			count++;
			if(max<count){
				start_index = i - count;
				max = count;
				end_index = i;
			}
		}
		else{
			count = 0;
		}
	}

	cout<<"---------------------------------------\n";
	cout<<"Longest Ascending Sequence:\n";
	cout<<"Length: "<<max + 1<<"\n";
	cout<<"Start index:"<<start_index<<", End Index:"<<end_index<<"\n";
	for(i = start_index ; i<=end_index ; i++){
		cout<<numbers[i]<<" ";
	}
	cout<<"\n";

	//--------For Descending--------------------------------------------------------------------------
	count = 0;
	max = 0;
	start_index = 0;
	end_index = 0;
	for( i = 0 ; i<n ; i++){
		if(numbers[i] == numbers[i - 1] - 1){
			count++;
			if(max<count){
				start_index = i - count;
				max = count;
				end_index = i;
			}
		}
		else{
			count = 0;
		}
	}

	cout<<"---------------------------------------\n";
	cout<<"Longest Descending Sequence:\n";
	cout<<"Length: "<<max + 1<<"\n";
	cout<<"Start index: "<<start_index<<", End Index: "<<end_index<<"\n";
	for(i = start_index ; i<=end_index ; i++){
		cout<<numbers[i]<<" ";
	}
	cout<<"\n";
	cout<<"---------------------------------------\n";

	return 0;

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int main(){
	vector<int> numbers;
	int n, num, i;
	int start_index, end_index, max = 0, count = 0;
	
	//User Input
	cin>>n;
	for( i = 0 ; i<n ; i++) {
		cin>>num;
		numbers.push_back(num);
	}

	//--------For Ascending---------------------------------------------------------------------------
	for( i = 0 ; i<n ; i++){
		if(numbers[i] == numbers[i - 1] + 1){
			count++;
			if(max<count){
				start_index = i - count;
				max = count;
				end_index = i;
			}
		}
		else{
			count = 0;
		}
	}

	cout<<"---------------------------------------\n";
	cout<<"Longest Ascending Sequence:\n";
	cout<<"Length: "<<max + 1<<"\n";
	cout<<"Start index:"<<start_index<<", End Index:"<<end_index<<"\n";
	for(i = start_index ; i<=end_index ; i++){
		cout<<numbers[i]<<" ";
	}
	cout<<"\n";

	//--------For Descending--------------------------------------------------------------------------
	count = 0;
	max = 0;
	start_index = 0;
	end_index = 0;
	for( i = 0 ; i<n ; i++){
		if(numbers[i] == numbers[i - 1] - 1){
			count++;
			if(max<count){
				start_index = i - count;
				max = count;
				end_index = i;
			}
		}
		else{
			count = 0;
		}
	}

	cout<<"---------------------------------------\n";
	cout<<"Longest Descending Sequence:\n";
	cout<<"Length: "<<max + 1<<"\n";
	cout<<"Start index: "<<start_index<<", End Index: "<<end_index<<"\n";
	for(i = start_index ; i<=end_index ; i++){
		cout<<numbers[i]<<" ";
	}
	cout<<"\n";
	cout<<"---------------------------------------\n";

	return 0;

This is in Java but it work

void printLongestIncSub(int a[])
{
int max = -1;
		int c = 0;
		int end = 0;
		int strt=0;
		

		for (int i = 1; i < a.length; i++) {
			if (a[i - 1] < a[i]) {

				c++;
				
				if (max < c) {
					max = c;
					end = i;
					strt=end-max;
					
				}
			} else {

				c = 0;

			}

		}
		System.out.println("Longest Ascending Subsequence");
		for(int i=strt;i<=end;i++)
		{
			System.out.print(a[i]+" ");
		}
}