## Interactive Brokers Interview Question

Software Engineer / Developerssuppose 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]+" ");
}
}
```

Sort the vector first, and then looking fo the longest subsequence?

- Zero June 25, 2011The solution works, but not the one that interviwer expects...