arrays - How to print the actual bitonic subsequence? -

given array arr[0 … n-1] containing n positive integers, subsequence of arr[] called bitonic if first increasing, decreasing. write function takes array argument , returns length of longest bitonic subsequence.

input arr[] = {1, 11, 2, 10, 4, 5, 2, 1}; output: 6 (a longest bitonic subsequence of length 6 1, 2, 10, 4, 2, 1)

now, finding out length, calculated first length of lis (longest inc. subsequence) , length of lds (longest dec. subsequence) , traversed on both arrays, while doing max(lis[i] + lds[i]-1) i varies 0 (n-1).

for ( = 0; < n; i++ )   // code lis {     ( j = 0; j < i; j++ )     {         if (arr[i] > arr[j] && lis[i] < lis[j] + 1)             lis[i] = lis[j] + 1;     } }  ( = 0; < n; i++ )   // code lds {     ( j = 0; j < i; j++ )     {         if (arr[i]  < arr[j] && lds[i] < lds[j] + 1)             lds[i] = lds[j] + 1;     } } 

now, if asked print actual bitonic subsequence, how can that? 1 way thought of find out index maximum occurs. now, know values of lis , lds @ index , then, print lis , lds index. but, couldn't formulate idea properly.

your idea spot-on. when compute maximum length max(lis[i] + lds[i]-1), store i of actual maximum, sequence changes increasing decreasing. let's call maxindex.

now can produce sequence follows:

• start @ prev=maxindex, i=maxindex-1, , go down in order of decreasing indexes until find lis[i]==lis[prev]-1 && arr[i] < arr[prev].
• store arr[i] in result list res, set prev=i, , continue searching down array
• stop when reach lis[i]==1.
• invert res list
• add arr[maxindex] res
• start @ prev=maxindex, i=maxindex+1, , go array until find lds[i]==lis[prev]-1 && arr[i] < arr[prev]
• store arr[i] in result list res, set prev=i, , continue searching down array
• stop when reach lds[i]==1.

this approach uses lis , lds arrays reconstruct both portions of bitonic sequence. since first part of sequence needs retrieved in reverse order, portion of list 0 maxindex needs reversed.