Question $3(26$ points, $20,6$ points$)$: Consider the length of a longest increasing subsequence

problem: Let A be an array of n positive integers. An increasing subsequence is some sequence A$[$i$1],$

A$[$i$2],...,$ A$[$ik$]$ such that A$[$i$1]<$ A$[$i$2]...<$ A$[$ik$]$ and i$1<$ i$2...<$ ik$.$

Example:

A $=\{10,3,9,1,20,2,5,40,30\}$

The length of the longest increasing subsequence is $4$ which is $1,2,5,40$ or $1,2,5,30.$

$1)$ Write the dynamic programming algorithm.

$2)$ What is the time complexity of the algorithm.