فرض کنید $A$ آرایه‌ای به طول $n$ است. از روی $A$ آرایه $B$ را به این صورت تعریف می‌کنیم. به ازای هر $i$ $(0 \leq i < n)$, $B[i]$ برابر بزرگترین عددی مانند $j$ است که $0 \leq j < i$ و $A[j] < A[i]$. در صورتی که عددی مانند $j$ با خاصیت گفته شده وجود نداشت $B[i]$ برابر $-1$ است. حال آرایه $C$ را از روی آرایه‌های $A$ و $B$ به این صورت تعریف می‌کنیم. به ازای هر $i$ $(0 \leq i < n)$, $C[i]$ برابر بزرگترین عددی مانند $j$ است که $0 \leq j < B[i]$ و $A[j] < A[i]$. در صورتی که عددی مانند $j$ با خاصیت گفته شده وجود نداشت $C[i]$ برابر $-1$ است.

الگوریتمی از $O(n)$ ارائه کنید که از روی آرایه $A$ آرایه $C$ را به دست آورد.

• سوال بعد
• سوال قبل