2. (9 points) Given a length- n array of integers A, let f(A) denote the maximum sum of any collection of non-adjacent entries in A. Examples: If A=[1,3,6,4,5], then f(A)=A[2]+A[5]=8. If A=[3,8,4], then f(A)= A[2]=8. If A=[10,1], then f(A)=0. For any length- n array A and any integer i in {0,,n}, let Ai denote the length- i prefix of A, and let ai denote f(Ai) Write a recurrence that can be used to compute the sequence a0,,an in O(n) time. You do not need to justify your recurrence