حل تشریحی سوال شماره 47 دروس مشترک

دنباله $x_1,\dots ,x_k$ را دنباله خوب می نامیم، اگر به ازای i هر داشته باشیم $2x_i<x_{x-1}+x_{i+1}$ فرض کنید می خواهیم طول بزرگ‌ترین زیر دنباله $a_1,\dots ,a_n$ را طوری به‌دست آوریم که خوب باشد. به این منظور آرایه دو بعدی A را بدین شکل تعریف می‌کنیم: $A\left[i,J\right]$ برابر طول بزرگترین زیر دنباله خوب $a_i,\dots ,a_j$ فرض کنید $L\left(i,J\right)$ و $\overline{L}\left(i,j\right)$ به‌ترتیب برابر طول بزرگترین زیر دنباله صعودی و طول بزرگترین زیر دنباله نزولی دنباله $a_i,\dots ,a_j$ باشند. کدام رابطه زیر درست است؟