Problem : Bitonic Array
my solution : https://ide.codingblocks.com/s/391629
what’s wrong in this ?
Bitonic array(Array Problem)
Hey @samardeep don’t post multiple doubts eply on single doubt as all your bitonic sub array doubts are with me. See i told you the issue is with the implementation. Read this detailed description
consider an index i .
if u know longest increasing sequence thats ends at i and longest decreasing sequence that starts from i then finding bitonnic sequence with i as pivot will be easy right?
it l1 is length of longest increasing sequence ending at i.
if l2 is length of longest decreasing sequence starting from i
then bitonnic length with pivot i will be l1 + l2 -1 (-1 becuase we have consider i in both the sequence )
now if we repeat this process for all values of i { 0 … n-1 } and pick maximum of all it will be our answer right?
how to construct increasing / decreasing array?
if u r at index i then u can add it to sequence ending at index i-1 only when a[i] > a[i-1] right ? becuase then only the sequnce will be increasing.
so in that case increasing[i]= 1+ increasing[i-1]
this is what they are doing
same logic holds for decreasing array
implementation details->
we will maintain two array lets say dec and inc .
value at ith index of inc array will tell the longest increasing subarray ending at ith index.
value at ith index of dec array will tell u longest decreasing subbarray starting from ith index.
Now after constructing these two array we can answer this problem easily
we will iterate from i=0 to i=n-1 and store maximum value of inc[i]+dec[i]-1
And as far as your code will fail this test case
1
10
3 4 1 5 8 3 2 2 10 6
In this expected output is: 6
Yours is giving: 5
Also take reference from this code as it will pass all test cases
please view my recent code, i have passed only one test case.
please don’t get offend, but i want to know what’s wrong in my approach?
No i am not getting offended . Let me dry run your approach and will tell you. Though i have given you test cases which you are failing you can consider that too. Just share me your updated code.
Just share your updated code too
https://ide.codingblocks.com/s/391663 you try your test cases here i tried and it passed every test case
This is the dry run of your code for test case
6 4 2 1 6 4 5 2 8
In this expected answer should be 4
Yours is coming 3
Now i guess you will get to know where are you making mistake at
ohhh, i wrongly understood the problem, it says the subarray should entirely increase or decrease ,i thought the array should entirely increase or decrease or increase and decrease
Yes you got the problem right. that’s why i told you to do it. Nevertheless you can do it now. Also mark your doubt as resolved as all your doubts are cleared now for this problem
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.