\ex{\item \begin{enumerate}
\item Soit $M=(m_{i,j})_{(i,j)\in[1,n]^2}$ une matrice d'entiers.

On appelle escalier toute suite de cases $(i,j)$ adjacentes (par les 
côtés) croissante (c'est à dire telle que 
$m_{i_{k},j_{k}}<m_{i_{k+1},j_{k+1}}$).

Trouver un procédé algorithmique pour trouver le plus long escalier.

\item Trouver un algorithme en $\bigcirc (n^2)$ si on ajoute comme 
condition que les suite $(i_p)$ et $(j_p)$ sont croissantes.

\end{enumerate}\origine{}
\annee{}
\concours{}

\solution{ \begin{enumerate}
\item On définit une suite (finie) de matrice carrées d'ordre $n$ à 
valeur dans $\{0,1\}$ :

$A_{1}$ a tous ses coefficients égaux à $1$.

$(A_{p+1})_{i,j}$ est égal à $1$ si et seulement si $(A_{p})_{i,j}$ a 
un voisin valant $1$ et tel que $m_{i',j'}<m_{i,j}$.
(alors $m_{i,j}$ est l'extrémité d'un escalier de longueur $p$) Dès que 
$A_{k}=0$, $k-1$ est la longueur du plus long escalier. En remontant 
les matrices de la construction on peut alors expliciter un (les) 
escaliers de longueur $k-1$

La complexité est en $\bigcirc (n^4)$ (l'escalier a une longueur au 
plus $n^2$)

\item On construit une matrice ligne par ligne. On pose $a_{1,1}=1$ 
puis, pour tout $j$, $a_{1,j}=1+a_{1,j-1}$ si $m_{1,j}>m_{1,j-1}$ et 
$1$ sinon. Puis pour la ligne $i$ :

Si $m_{i,j}>m_{i-1,j}$ ou $m_{i,j}>m_{i,j-1}$, on pose $a_{i,j}=\max 
(1+m_{i-1,j},1+m_{i,j-1})$, $a_{i,j}=1$ sinon (on ne s'occupe que de 
$m_{i-1,1}$ si $j=1$ ). Le coefficient maximum de la matrice finale 
indique la longueur du plus grand escalier. On lit peut alors le 
remonter sur la matrice $A$.

\end{enumerate}}
}


