I have saved my code on coding blocks ide, it is working perfectly for the input case given, please tell why am I not getting a perfect answer. Also, suggest how to make it more efficient.
Bitonic Subarray
@Tushar-Goel-1587999611286693 your code gives wrong answer when the ending of a pattern has same entries
for example in case of
1
8
1 3 2 2 3 4 5 6
correct solution is 6 but your code is giving 5 because it ends its first increasing and decreasing pattern at second 2, to counter this you’ll have to backtrack till you find same element which’ll make the worst case time complexity of this code O(n^2) which will result in TLE so you’ll need to change the approach.
Correct Approach:
You can make 2 array, one inc, that will have at ith position length of the increasing sequence till i, similary a dec array that will have length of decreasing sequence till ith (ith till n).
For inc array compute the sequence length from left to right
For dec array compute the sequence length from right to left.
Now for every i you have both increasing length till that point and decreasing length to get answer.
Eg
1 6 8 9 3 4 6 5
inc array
1 2 3 4 1 2 3 1
dec array
1 1 1 2 1 1 1 2
Ans 4 + 2 -1
Here is link to code for reference purpose:
Please check the code