Bitonic max subarray

#1

i’m not sure where i’m going wrong.Help me debug.The code shows segmentation fault.

#2

Hey I checked your code
Its not giving segmentation error on my side ,please check if u have sent the right code.

#3

ya its working but the output is wrong everytime I run the code

#4

Here i did 6 corrections in your code


Correction 1 is done because your algo will always count 1 element less say we have 2 1 here a[0] >a[1] so count1 will be 0 but instead it should be 1
because atleast 1 element is there.
Correction 2 is done because if first loop does not run then k is not initialized for current subarray and k for some previous subarray will be used.
Correction 3,4,5,6 are to avaoid segmentation error when a[p+1] and a[k+1] does not exist also elements can be equal in sub array so added equality as well .

Current code will give u TLE for 2 test cases.
This can be done in O(n)

Approach for O(n)
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
max(1+1-1,2+1-1,3+1-1,…)
Ans 4 + 2 -1

1 Like
#5

Hey @armaanbhardwaj23
I hope your doubt is resolved ,if its then please mark it as resolved :slight_smile:
If its not then let me know the issue.

1 Like
#6

Thanks a lot for your help.You’ve really helped me a lot in pointing out my mistakes.Thank you so much!

1 Like