Biotonic subarray

#1

please provide some hint or line of thinking for the problem

#2

Hello @Bansaljatin05,

Let us consider the array {12, 4, 78, 90, 45, 23} to understand the soultion.

  1. Construct an auxiliary array inc[] from left to right such that inc[i] contains length of the nondecreaing subarray ending at arr[i].
    For A[] = {12, 4, 78, 90, 45, 23}, inc[] is {1, 1, 2, 3, 1, 1}

  2. Construct another array dec[] from right to left such that dec[i] contains length of non-increasing subarray starting at arr[i].
    For A[] = {12, 4, 78, 90, 45, 23}, dec[] is {2, 1, 1, 3, 2, 1}.

  3. Once we have the inc[] and dec[] arrays, all we need to do is find the maximum value of (inc[i] + dec[i] – 1).
    For {12, 4, 78, 90, 45, 23}, the max value of (inc[i] + dec[i] – 1) is 5 for i = 3.

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

1 Like
#3

I read same solution on geeks for geeks…
But didn’t get what length of increasing and decreasing array meant…
Can you show how lengths are computed with an example…

#4

Hey @Bansaljatin05,

Let’s understand the example:
{12, 4, 78, 90, 45, 23}

Rules:

  1. For the first element, the value is 1 for both inc[] and dec[].
    Reason:
    a sequence of a single element is both increasing and decreasing.

  2. for inc[] (from left to right)
    inc[0]=1 (for 12)
    2.1. when the next element is smaller than previous in the sequence i.e. non-increasing sequence. The length will be 1.
    inc[1]=1 (as a[0]>a[1]])
    2.2. when the next element is larger than previous in the sequence i.e. increasing sequence. The length of the increasing array will be length till previous element +1.
    inc[2]=inc[1]+1=2 (as a[1]<a[2])

    Following above
    inc[3]=3
    inc[4]=1
    inc[5]=1

  3. for dec[] (from right to left)
    dec[5]=1 (for 12)
    2.1. when the next element is larger than previous in the sequence i.e. decreasing sequence. The length of the decreasing array will be length till previous element +1.
    dec[4]=dec[5]+1=2 (as a[5]<a[4]])
    2.2. when the next element is smaller than previous in the sequence i.e. non-decreasing sequence. The length will be 1.
    dec[2]=1 (as a[2]<a[3])

    Following above
    dec[3]=3
    inc[1]=1
    inc[0]=2

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

1 Like