Question 4 - A Fantasy to Become Rich [35%] You visited a casino in Macau and played n rounds of a gambling game. You are unhappy with the total amount of money won. Suppose now a time machine appears, which allows you to go back to the past and play the game again starting at any of the n rounds. You can choose to leave the game at any round afterwards or play until round n. However, after leaving the game, you cannot join the game anymore. Your task is to design different algorithms to find the maximum amount of money you can win under such constraints. Assume that the input data is saved in a list S, which consists of n integers each representing the amount you win/lose in a round. The numbers are stored chronologically, starting with the result of the first round and ending with the result of the last round. Also, you may assume that there is at least one positive entry in the list S. For example, suppose your game result is S = [-2, 4, -3, 2, 3, -1, 2, -4, -3, 5]. You can win the maximum amount of money by joining the game at round 4 and leaving the game after round 7. Your net gain would then be +2+3-1+2= 6. (a) Design a recursive algorithm to solve the problem faster than O(n) time. Explain how your algorithm works. State and prove your algorithm's running time by setting up and solving a recurrence equation. (b) Design another algorithm to solve the problem in O(n) time and O(1) extra space. Explain how your algorithm works and prove it can run in O(n) time.