Let A be an array of length n containing real numbers. A longest increasing subsequence

$($LIS$)$ of A is a sequence $0<=$ i$1<$ i$2<...$ i$<$ n so that A$[$i$1]<$ A$[$i$2]<<$ A$[$i$],$

so that $$ is as long as possible. For example, if A $=[6,3,2,5,6,4,8],$ then an LIS is

i$0=2,$ i$1=3,$ i$2=4,$ i$3=6$ corresponding to the subsequence $2,5,6,8.($Notice that a

longest increasing subsequence does not need to be unique$).$ In the following parts, we

will walk through the recipe that we saw in class for coming up with DP algorithms to

develop an O$($n$2)-$time algorithm for finding an LIS.

$($a$)(2$ bonus points$)($Identify optimal sub$-$structure and a recursive relation$-$

ship$).$ We will come up with the sub$-$problems and recursive relationship for you,

although you will have to justify it$.$ Let D$[$i$]$ be the length of the longest increasing

subsequence of $[$A$[0],...,$ A$[$i$]]$ that ends on A$[$i$].$ Expain why

D$[$i$]=$ max

k $\{$D$[$k$]+1$ : $0<=$ k $<$ i$,$ A$[$k$]<$ A$[$i$]\}.$

$[$Provide a short informal explanation. It is good practice to write a formal

proof, but this is not required for credit