Socialcam Interview Question
Country: United States
You can do it better with recursion, split the sequence, determine the longest increasing/decreasing sub-sequence and remember if the longest sub-sequence was at the beginning or ending of the sequence. And when "merging" the result just add the "longests" (ending of 1st+starting of 2nd forms a consequtive sub-sequence) or choose the max of them (otherwise).
logic::
while traversing array,
use 2 bool variables,
bprev => relation [ascending/descending] between current & prev elements i.e.a[i-1] & a[i]
bcur => relation [ascending/descending] between current & next elements i.e.a[i-1] & a[i]
if bprev == bcur
increment counter
else
there is change, so prevcounter = max of curcounter and prev counter
curcounter ++
return max counter +1
code
#include "iostream"
using namespace std;
int maxAscDeslength(int a[],int n)
{
int prevcounter =0 ,curcounter = 0;
bool bprev = true;
if(a[0] > a[1])
bprev = false;
bool bcur;
for(int i =0; i< n-1; ++i)
{
if(a[i] < a[i+1])
bcur = true;
else
bcur = false;
if(bprev != bcur)
{
prevcounter = max(prevcounter,curcounter);
curcounter = 1;
}
else
curcounter++;
bprev = bcur;
}
return (max(curcounter,prevcounter)+1);
}
int main (){
int a[] = {3, 5, 8 , 9, 3, -1, -4, -5, -6};
cout << maxAscDeslength(a,9);
return 0;
}
int longestAscendingSub(int A[], int m)
{
int startAsc = 0;
int endAsc = 0;
int startDec = 0;
int endDec = 0;
int longest = 0;
for (int i = 1; i < m; ++i)
{
if (A[i] > A[i - 1])
{
startDec = i;
endAsc = i;
}
else if(A[i] < A[i - 1]){
endDec = i;
longest = longest < (endAsc - startAsc + 1) ? (endAsc - startAsc + 1) : longest;
longest = longest < (endDec - startDec + 1) ? (endDec - startDec + 1) : longest;
startAsc = i;
}
}
return longest;
}
- bluesky September 26, 2012