#include <bits/stdc++.h>
using namespace std;
int helper(int i, vector<int> &h, vector<int> &l, vector<int> &r, vector<int> &dp)
{
if (i == -1 or i == h.size())
return 0;
if (dp[i] != -1)
return dp[i];
dp[i] = 1 + max(helper(l[i], h, l, r, dp), helper(r[i], h, l, r, dp));
return dp[i];
}
int main()
{
int n;
cin >> n;
vector<int> h(n), l(n, -1), r(n, n), dp(n, -1);
for (int i = 0; i < n; i++)
cin >> h[i];
stack<int> st;
for (int i = 0; i < n; i++)
{
while (!st.empty() and h[st.top()] < h[i])
{
l[i] = st.top();
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; i--)
{
while (!st.empty() and h[st.top()] < h[i])
{
r[i] = st.top();
st.pop();
}
st.push(i);
}
int ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, helper(i, h, l, r, dp));
cout << ans;
return 0;
}
Fails for something similar to this.
Best solution : 4 -> 3 -> 2 -> 1
Your solution : 3 -> 2 -> 1
Hope it helps :)
Thanks a lot man!
this is a really good problem and its solvable without segment trees, unlike what codeforces would lead you to believe. think about the order and you'll probably get it (considering that i was able to), tho your solution is interesting. what if we go to the smallest but still greater left/right element instead?