In a previous problem, we considered a hopping game where you can hop 1, 2, 3, or 4 spaces forward and spaces are marked either O or X (where O is safe and X is an obstacle which makes you lose the game.)

Now lets say that spaces have penalties and rewards. More precisely, each space i has a value vi which can be the following

vi = : This space has an obstacle which makes you lose if you land on it.

vi < 0: This space does not have an obstacle, but you pay a penality vi if you land on it.

vi = 0: This space does not have an obstacle, incurs no penality, but also offers no reward.

vi > 0: This space does not have an obstacle, and you receieve a reward of value vi for landing on it.

Design an algorithm running in time O(n) to determine the largest amount of reward you can pick up while reaching the end (square n) from the beginning (square 0, assumed safe) in at most n hops. Prove your algorithms correctness and efficiency