Consider the following problem: Input: An array Ai...n of integers Output: The largest integer m such that the array A[1...n] has subsequence of length m which is strictly increasing. The following pseudocode finds the length of the longest of the given array A[i...n] by considering all possible subsequences: Algorithm 1 longestSubSeq( int A[1...n] ) 1: k = 0; 2: while (true) do 3: //(I) The longest increasing subsequence of A has length C[i+1] ) then return false; end if i++; 7: end while 8: return true; Example: longest SubSeq( [2, 4, 3, 8,5,5,6,7,9] ) returns 6 Justification: (2, 4,%.8.5,5,6,7,9] = [2, 4, 5, 6, 7, 9) which is a longest increas- ing subsequence of the original array. (1) (2 points) Consider running longest SubSe on the array: [119, 100, 112, 125, 113, 110, 130, 115, 120] What does longest SubSeq return and what array B causes this return? (2) (4 points) Use induction to prove the loop invariant (1) is true and then use this to prove the correctness of the algorithm. Specifically complete the following: (a) Base case (b) Inductive step (Hint: you can assume that the inner loop correctly iterates through all possible choices of how to remove k elements from A.) c) Termination step (Hint: the outer loop never terminates but consider what can you say about the k value that causes us to return.) (3) (1 point) Give the best-case runtime of longestSubSeq in asymptotic (i.e., 0) notation as well as a description of an array which would cause this behavior. (4) (1 point) Give the worst-case runtime of longest SubSeq in asymptotic (i.e., O) notation as well as a description of an array which would cause this behavior