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.