Nearest Consecutive Local Peaks
National Olympiad — Municipal round (2022 season)
Submission name: lokmax.cpp
Problem summary
Within the prefix ending at the first zero inclusive, minimize intervening elements between consecutive strict interior peaks.
Input
N and N signed values.
Output
Minimum gap, or zero if fewer than two peaks exist.
Constraints
3≤N≤100000; −10^9≤a[i]≤10^9.
Worked example
Input and output for the worked example discussed below.
Input
7 1 3 -1 5 0 7 4
Output
1
Solution analysis
- Record the first zero as the prefix boundary while still reading all input. If none appears, use the entire sequence. Only interior positions can be peaks.
- A peak exceeds both immediate neighbours strictly. Keep the last peak index and minimize current−previous−1 as new peaks appear.
- The sample prefix is [1,3,−1,5,0]. Its peak positions2 and4 have one intervening value. The later7 is outside the examined prefix.
Why it works
The scan tests exactly eligible positions and encounters peaks in order. Each new peak and its stored predecessor form exactly one consecutive-peak pair.
Complexity: O(N) time and O(N) space.
Watch out. Equal neighbours do not make a peak. Exclude endpoints and subtract one from index differences.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// The scan tests exactly eligible positions and encounters peaks in order.
int main(){
int n;
cin>>n;
vector<long long>a(n);
int length=n;
bool found=false;
for(int i=0;i<n;i++){
cin>>a[i];
if(!found&&a[i]==0){
length=i+1;
found=true;
}
}
int previous=-1,answer=n;
for(int i=1;i+1<length;i++){
if(a[i]>a[i-1]&&a[i]>a[i+1]){
if(previous!=-1){
answer=min(answer,i-previous-1);
}
previous=i;
}
}
cout<<(answer==n?0:answer)<<'\n';
}