### 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 :

Psychos in a Line
•  » » 16 months ago, # ^ |   +20 If you go through some $dp_x$ one time in find_ans function you will never check it again.