### Fype's blog

By Fype, 16 months ago, Problem : You have an array a of size $n$. for each $i$ (${i \le n}$) you have to find maximum $j$ such that ${1 \le j < i}$ and ${a_j > a_i}$ and if there is no $j$, consider the answer for $i$ equal to $0$, solve the problem with total complexity ${O(n)}$.

Solution 1 : Of course there is an easy solution using stack.

for (int i = 1; i <= n; i++) {
while (s.size() && a[s.top()] <= a[i])
s.pop();
if (s.size())
L[i] = s.top();
s.push(i);
}


Solution 2 : About 2-3 month ago I suggested a dp solution for this problem and i never thought that it would be ${O(n)}$ but here I am sharing it with you :D
${dp_i = }$ answer for i.
So how can we update this dp?!, let's check maximum $j$ that can be the answer for $dp_i$. It's obvious that if ${a_{i - 1} > a_i}$ the answer is $i - 1$.
what if ${a_{i - 1} \le a_i}$ : then the answer isn't in range $(dp_{i - 1}, i]$ so the next number we should check is $dp_{i - 1}$ and if it wasn't answer that we need we should check $dp_{dp_{i - 1}}$, and then $dp_{dp_{dp_{i - 1}}}$ and so on.
Do you see the pattern?! :D

int find_ans(int i, int j) {
if (!j)
return j;
return (a[j] > a[i]? j: find_ans(i, dp[j]));
}
for (int i = 1; i <= n; i++)
dp[i] = find_ans(i, i - 1);


some problems :

Task Postering (pla)
Psychos in a Line
Task Little Bird (pta)
These problems aren't necessarily the exact problem but the main idea is same. #dp, Comments (5)
 » Why it is O(n)?
•  » » If you go through some $dp_x$ one time in find_ans function you will never check it again.
 » I think the idea between the two solutions is the exact same. It just so happens that the implementation of the stack is different (instead of explicitly maintaining the stack, you simulate it through back pointers). This is also described here.
•  » » 16 months ago, # ^ | ← Rev. 2 →   yeah, I know and it was cool the first time I came up with it. I didn't check if it was in Wikipedia or not, I just checked codeforces, sorry :D
•  » » » It was cool the first time I came up with itWell. This technique has been around since ages. GeeksforGeeks documents this technique under "Next greater element". This technique also appears in the coding interview question: Maximum area in a histogram.