(20 points) 1. For this problem consider the Maximum problem stated below. Maximum Input: A sequence of n integers A= (a1, a2,..., an). Output: a A such that a aj for all aj e A. (4 points) a) Using pseudocode state an algorithm that solves the Maximum problem using a loop. (4 points) b) Identify the loop invariant for the loop in your algorithm that will help you prove your algorithm is correct. That is, state the loop invariant as a proposition of the kind "After iteration i of the loop...". (8 points) c) Using induction prove that your loop invariant holds for each iteration i. (4 points) d) Using the loop invariant show that your algorithm is correct.