$(25$ points$)$ Consider a two$-$dimensional array A$[1$::n; $1$::n$]$ of distinct in$-$

tegers. We want to nd the longest increasing path in A$.$ A sequence

of entries A$[$i$1$; j$1]$;A$[$i$2$; j$2]$; : : : ;A$[$ik; jk$]$;A$[$ik$+1$; jk$+1]$; : : : is a path in A if

and only if every two consecutive entries share a common index and the

other indices dier by $1,$ that is$,$ for all k$,$

either ik $=$ ik$+1$ and jk$+12$ fjk $1$; jk $+1$g$,$ or

jk $=$ jk$+1$ and ik$+12$ fik $1$; ik $+1$g$.$

A path in A is increasing A$[$i$1$; j$1]$;A$[$i$2$; j$2]$; : : : ;A$[$ik; jk$]$;A$[$ik$+1$; jk$+1]$; : : :

if and only if A$[$ik; jk$]<$ A$[$ii$+1$; jk$+1].$ The length of a path is the number

of entries in it$.$

Design a dynamic programming algorithm to nd the longest increasing

path in A$.$ Your algorithm needs to output the maximum length as well

as the indices of the array entries in the path. Note that there is no

restriction on where the longest increasing path may start or end. De$-$

ne and explain your notations. Dene and explain your recurrence and

boundary conditions. Write your algorithm in pseudo$-$code. Derive the

running time of your algorithm.