Question 3 Finding maximum element (5 points) re glven an array 4 of sizge n. The first k elements are in strict increasing order, le. for is k, AlAlU +1]. The remaining n-k elements are in strict decreasing order, i.e., for k + lsisn, Al-1A. k is unknown. In other words, Ak] is the maximum element in a. Give a naive algorithrn that runs in (n) time to find k. FINDMAX-NAIVE(A, 1, n) b. Give an algorithm of the same function that runs in 0(lgn) time. Write two pseudocode implementations: a recursive one and an iterative (i.e., non-recursive) one. Hint: Use the similar method that is used for binary search (from assignment 1), considering the relationship between A[k] with its neighbor elements. Recursive implementation FINDMAX-RECURSIVE(A, 1, n) Iterative implementation FINDMAX-ITERATIVE(A, 1, m)