Alice is freelancing for an online company. for each day i she works, she earns vi>=0 dollars. However, she can program for at most 4 consecutive days, but then she must take a day of rest. Given the payoffs v1, v2,..., vn for each day, Alice must decide which days to work and which days to take rest, so as to maximize her total payout at the end of n days, and not work more than 4 days in a row.

(a) Give an example with n = 6 for which the optimal schedule has Alice rest on the first day.

(b) Give an example with n = 10 where the optimal schedule has Alice rest on two consecutive days.

(c) Construct a O(n) dynamic programming solution which computes the optimal schedule and the total amount of money Alice will make without her having to work more than 4 days in a row. You should specify: (1) the recursive problem specification, (2) the base case, and (3) the order in which the subproblems are comuted. Reason why the method is O(n).