Problem 4. Consider the longest increasing subsequence problem: given a sequence of n distinct numbers A[1,..., n], we would like to find the longest increasing subsequence of A. For example, A = (5, 2, 6, 7, 1,9) has an increasing subsequence of length four as marked; note that the longest increasing subsequence is not necessarily unique. Reduce the longest increasing subsequence to the problem of finding the longest path in a directed graph: suppose you have a black box that can find the longest path of any DAG in O(1) time, how would you use it to solve the longest increasing subsequence. Analyze the running time of your algorithm, and prove that it is correct assuming the black box correctly returns the longest path of any DAG