Consider the following problem: Given a sequence of integers, find the longest subsequence whose elements are in increasing order. More concretely, the input is an integer array $\backslash ($ A$[1\backslash$ldots n$]\backslash ),$ and we need to compute the longest possible sequence of indices $\backslash (1\backslash$leq i$\_\{1\}$n$)$ return $0$ ;

else if $($A$[$i$]>=$A$[$j$])$ return f$($i$,$j$+1)$ ;

else $\{$

int skip $=$ f$($i$,$j$+1)$ ;

int take $=1+$f$($j$,$j$+1)$ ;

return max$($skip$,$take$)$ ;

$\}$

$```$

Which can be implemented dynamically using the following algorithm:

$```$

function g$($A$[1..$n$])\{$

A$[0]=-\backslash$infty

for i $=0$ to n

L$[$i$][$n$+1]=0$

for j $=$ n downto $1$

for i $=0$ to j$-1$

keep $=1+$ L$[$j$][$j$+1]$

skip $=$ L$[$i$][$j$+1]$

if A$[$i$]\backslash$geq A$[$j$]$

L$[$i$][$j$]=$ skip

else

L$[$i$][$j$]=$ max$($keep$,$skip$)$

$```$

a$)$ Modify the dynamic algorithm so that you can remember if you want to "keep" or "skip" each number.

b$)$ Code the modified dynamic algorithm in C or Java.

c$)$ Write function printSolution$($int A$[],$ int n$)$ which calls your implementation above and then print the numbers in the longest increasing sub$-$sequence. The sub$-$sequence must be printed in the order it appeared in the original sequence $($from lowest index to highest.$)$