問題詳情

8. (8 points) Given a sequence of n integers A = (a1, a2,..., an), the longestincreasing subsequence problem is to find a longest subsequence

alkFor 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(n2) timealgorithm for solving the longest increasing subsequence problem. Please alsojustify your algorithm and its time complexity.

參考答案