https://codeforces.com/problemset/problem/1341/B
i approached this question by sliding window method but not getting correct output, please check my code and tell me how to correct my code
Not getting correct ans
hello @shivamgoel150
u need to handle the corner vertices carefully.
for example when u have considered [i…i+k-1] window then peak leaf is using i-1 index which is wrong .
refer editorial code for implementation
sir i didn’t understand can you please explain with code implementation
Let’s make an array consisting of 00 and 11, such that it shows whether the position ii is a peak on the whole segment. To do this, we will go through the indices from 22 to n−1n−1, and if the conditions ai−1<aiai−1ai+1ai>ai+1 are true, then we write 11 in a new array at position ii. After that, we calculate the prefix sum in the new array prefpref. Now the number of peaks in the segment [l,l+k−1][l,l+k−1] is calculated as pref[l+k−2]−pref[l]pref[l+k−2]−pref[l], so we find out how many peaks in the desired segment, not including the boundaries of the segment. It remains only to go through all ll from 11 to n−k+1n−k+1 and find the leftmost ll, such that pref[l+k−2]−pref[l]pref[l+k−2]−pref[l] as much as possible.
pls refer code implementation from here->
https://codeforces.com/contest/1341/submission/77904408
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.