Guidelines for submission: If your algorithm is based on dynamic programming, then you must write your solution using the following format in that order.
• Subproblem definition.
• Recurrence of the subproblem.
• The specific subproblem(s) that solves the actual problem.
• Algorithm description.
• Explanation of the running time of your algorithm.
Problem: Farmers Boggis, Bunce and Beans have set-up an obstacle course for Mr. Fox. The course consists of a long row of booths, each with a number written at the door of the booth. Formally, Mr. Fox is given an array A[1,2, . . . , n] where A[k] denotes the number written at the door of the k-th booth. Each number A[k] can be positive, negative or zero. Everybody agrees to the following rules.
• At each booth, Mr. Fox must say either RING or DING.
• If Mr. Fox says RING at the k-th booth, then he earns a reward of A[k] chickens if A[k] > 0 and pays a penalty of −A[k] chickens if A[k] < 0.
• If Mr. Fox says DING at the k-th booth, then he earns a reward of A[k] chickens if A[k] < 0 and pays a penalty of −A[k] chickens if A[k] > 0.
• Mr. Fox is forbidden to say the same word more than three times a row. What it means is that if Mr. Fox says RING in booths 5, 6, and 7, then Mr. Fox must say DING at booth 8. Conversely if Mr. Fox says DING in booths 6, 7, 8, then he must say RING at booth 9.
• All accounts will be settled at the end after Mr. Fox visits every booth in the order given and the umpire calls “Hot Box”. Mr. Fox will not have to carry chickens through the obstacle course.
• Finally, if Mr. Fox violates any of the rules, or if he ends the obstacle course owing the farmers chickens, the farmers will shoot him.
Design an efficient algorithm that computes the largest number of chickens that Mr. Fox earns by running the obstacle course given the array A[1,2, . . . , n] of numbers as the input. The running time of your algorithm must be polynomial in n.
1
