Given an array of integers A [0...n-1), consider the following puzzle: pick elements of A to obtain the largest possible sum, subject to the constraint that you cannot pick 3 or more elements in a row. For example, if the array were A = (2,3,3,2, -1], then the largest sum we could get is A[0] +A[1] +A[3] = 2 +3+2 = 7; we can't pick index 2 instead of (or in addition to) 0 to get a larger sum since we would then have picked 3 elements in a row. Let's solve this puzzle using dynamic programming. (a) (30 pts.) Let S(i) be the largest possible sum one can get when picking elements of A[O...), without picking > 3 elements in a row. Derive a recursive formula for S(i), making sure to include any base cases. (b) (20 pts.) Based on your answer to part (a), describe an efficient algorithm to solve the puzzle. Your algorithm should return the list of indices to pick. (c) (10 pts.) What is the asymptotic runtime of your algorithm