1.) Let A[1....n] be an array of n positive integers, Let B[1...n] be the n elements of A in sorted order. For example, if A = 5,3,4,1,2 then B = 1,2,3,4,5. Prove that the longest increasing subsequence (LCS) in A is the same as the longest common subsequence (LCS) between A and B. That is LIS(A) = LCS(A,B).

a) Let c1.....,ck be an increasing subsequence of A. Show that c1......,ck is a common subsequence of A and B. b) Let c1.....,ck be a common subsequence of A and B. Show that c1......,ck is an increasing subsequence of A