Techgig July contest : Bitonic Sequence : Level(Easy)

Problem Statement

You are given an array A[] containing n positive integers. Lets define Bitonic subsequence. A subsequence of array A[] is called Bitonic if it is first strictly increasing and then strictly decreasing. Your task is to find the length of largest bitonic subsequence given an array.

Note- A sequence sorted in increasing order is considered as Bitonic with decreasing part as empty. Similarly, A sequence sorted in decreasing order is also considered as bitonic with increasing part as empty

How many of you guys have got the solution for this problem ?

Well, I have got the logic which work perfect but unfortunately It doesn`t fetch 100 on the Techgig compiler. The problem is not with my Code/Loigc but the problem is Techgig`s definition for Bitonic subsequence. Which can be found here

Techgig say that the sequence should be strictly increasing and then decreasing where as it can be either way and that too in circular fashion.

If you refer the previous link we can see that

3 5 8 9 7 4 2 1

5 8 9 7 4 2 1 3

both are bitonic such that 2nd sequence can be converted to first by a circular shift.

Lets, come to the basic question on Techgig and see how to implement a logic for it.

I am considering a sequence for example given below.

9,10,1,3,5,8,2,1,7,5,3,1

Here starts the actual logic :-

As we want an subsequence which is first increasing and then decreasing let find the increasing numbers.

We will be going number by number.

step 1 : Consider 9, It is the first number so directly put it into a list(Array)

             9 (List)

step 2: next is 10, since 10 is greater and 9, put it into same list

            9,10

step 3: 1, since 1 is less than 10 and we are searching for increasing number, we will create a new list

           9,10

           1

           At this point, If we had any numbers less then 1 in the previous list then those needed to be first      i inserted in the new list and then 1. But we didnt have any here

step 4: Once we have more than 1 list, every new number has to be checked with the last number of that list and if the new number is greater then it has to be appended to that list. The next number is 3,first check in the previous list if 3 is greater than the last number if it. In our case we have 10 as the last number so we need not append 3.

Now, 3 is greater than 1, so just append it.

           9,10

           1,3

Repeat the above steps, we get

          9,10

          1,3,5,8

          1,2

          1,7

          1,5

          1,3

          1

These are the various lists which we get. Now we can see here that 2nd list has the largest length. But that wont help us, because it may happen the there is not decreasing subsequence for it or may be some other list has a decreasing sequence of greater length.

Hence, once these lists are formed we perform a similar process for decreasing lists.

The important thing to keep in mind is the position(in input1[]) of last number in our lists.Because, we need to find the decreasing sequence only after that position.

For example, lest take our first list 9,10 and try to find the various decreasing sequences for it.

step 1 :1

step 2: 1

           3

step 3: 1

           3

           5   

step 4: 1

           3

           5

           8

step 5: 1

           3,2

           5,2

           8,2

step 6: 1 

           3,2,1

           5,2,1

           8,2,1

step 7: 1 (Important)

           3,2,1

           5,2,1

           8,2,1

           8,7

step 8: 1 (Important)

           3,2,1

           5,2,1

           8,2,1

           8,7,5,3,1

Now, we can see that for increasing order 9,10; we have a decreasing order 8,7,5,3,1 of length 5, so 5+2=7 is the length of this Bitonic.

Similarly, we can find the decreasing sequences for other lsit`s generated in part I and check the largest length.

           

Hope this was helpful. There may be other logic for the implementation but this was my own from scratch.

Also, this can be modified for the circular sequence.

If anyone want the code for this just put a comment below, and I would share the same.

Continue