申論題

8. (8 points) Given a sequence of n integers A = (a₁, a₂,..., a_n), the longest increasing subsequence problem is to find a longest subsequencealk For example, (1,2,5,8) is a longest increasing subsequence of (4,1,7,5,2,5,8,4). Please use the dynamic programming technique to design an O(n²) time algorithm for solving the longest increasing subsequence problem. Please also justify your algorithm and its time complexity.