Maximum length bitonic subsequence

#1


getting wrong answer in all testcases.
pls tell correct code.

#2

Hello @yutikakhanna,

Follow this approach:
Consider the given array arr={12,4,78,90,45,23}

  1. Construct an array increasing[] such that increasing[i] will contain the length of non decreasing subarray ending at arr[i] from LEFT TO RIGHT manner. Therefore for the given array increasing[]={1,1,2,3,1,1}

  2. Construct another array decreasing[] from RIGHT TO LEFT manner of the given array such that decreasing[i] contains length of non-decreasing subarray starting at arr[i].Note that this is non-decreasing from backward direction or in RIGHT to LEFT manner…so it will actually be decreasing as seen from LEFT to RIGHT manner. So decreasing[]={2,1,1,3,2,1}

  3. Start iterating the increasing[] and decreasing[] array. The maximum of (increasing[i]+decreasing[i]-1) will be the maximum length of biotonic subarray. Here it is 5 for i=3.
    Hope this helps.

Hope, this would help.
Give a like if you are satisfied.

#3

pls tell in the form of a code.

#4

Sure @yutikakhanna,

relate above with the following code:

Give a like if you are satisfied.

1 Like
#5

all the testcases are showing wrong in this code

#6

Hello @yutikakhanna,

The reason why your code mine is not working for this question is that here you are required to find a sub sequence instead of a subarray.
The logic i have specified would work for subarrays.

Difference?
Let s=“abc” be a string.
“ac” is a subsequence but not a substring.

Try to think of a different approach.

Hope, this would help.

#7

pls share the code for the sub sequence…i am unable to do it.

#8

@S18ML0016 hey apke left se LIS nikalte hue logic me galti hai similiarly right side se kyunki ye subsequence hai not subarray,her is code for refernce ,I have corrected it:


Hope you get it.

#9

Hey @rishabhmahajan546,

I pointed out the same in my last reply.
BTW, thanks for sharing the code.
@yutikakhanna, you may refer to the code @rishabhmahajan546 has shared.

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.