Proficient.
Put your skills to the test.

Problem summary

Spider-Man may start on any building in a row. From building i he can jump to j if h[j] is strictly higher than h[i] and every intervening building. Find the maximum number of buildings in a training sequence.

Constraints

1 ≤ N ≤ 2·10⁵; 1 ≤ h[i] ≤ 10⁹.

Worked example

An independently prepared example for this explanation.

10
20 15 17 35 25 40 12 19 13 12

5

Solution analysis

1. First consider only jumps to the nearest strictly higher building on either side. Both are legal: all intervening heights are at most the source height. Two monotone-stack passes find these neighbors, popping heights at most the current height.
2. These restricted jumps suffice for an optimum. Any legal jump to a farther higher building can be replaced by consecutive nearest-higher jumps toward it. The chosen destination remains higher than every intermediate building, so this chain must reach it and only adds visited buildings. Thus deleting all farther jumps cannot reduce the maximum achievable length.
3. The two retained edges per building lead strictly upward in height. Process buildings in decreasing height order and set dp[i]=1+max(dp[leftHigher],dp[rightHigher]), ignoring missing neighbors. For the example, the chain with heights 15,17,20,35,40 visits five buildings. The answer is the largest dp value.

Why it works

Nearest-higher neighbors are legal destinations. For any farther legal destination, repeated nearest-higher jumps in its direction stay before or at it and strictly increase height, so eventually reach it. Replacing every long jump this way produces a path in the retained graph with at least the original number of visits. Hence its maximum equals the original maximum. The graph is acyclic by strict height increase, and the decreasing-height DP evaluates its longest-path recurrence correctly.

Watch out. The destination must be strictly higher; equal buildings are popped while finding neighbors. Count the starting building. Do not restrict jumps to adjacent positions.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
// Algorithm: First consider only jumps to the nearest strictly higher building on either side.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>height(n),left(n,-1),right(n,-1),stack,order(n),dp(n,1);
    for(int&value:height){
        cin>>value;
    }
    for(int i=0;i<n;++i){
        while(!stack.empty()&&height[stack.back()]<=height[i]){
            stack.pop_back();
        }
        if(!stack.empty()){
            left[i]=stack.back();
        }
        stack.push_back(i);
    }
    stack.clear();
    for(int i=n-1;i>=0;--i){
        while(!stack.empty()&&height[stack.back()]<=height[i]){
            stack.pop_back();
        }
        if(!stack.empty()){
            right[i]=stack.back();
        }
        stack.push_back(i);
    }
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](int a,int b){
        return height[a]>height[b];
    });
    int answer=1;
    for(int i:order){
        if(left[i]!=-1){
            dp[i]=max(dp[i],1+dp[left[i]]);
        }
        if(right[i]!=-1){
            dp[i]=max(dp[i],1+dp[right[i]]);
        }
        answer=max(answer,dp[i]);
    }
    cout<<answer<<'\n';
}