The problem:
There is a set of n days that Bob is planning to work, and on each day i
there is a mission; each mission lasts exactly one day, must be done on day i
in which it is given, and pays bob x_i
dollars. Bob cannot work more than 5 consecutive missions at a time. That is, he must take at least 1 rest day every 5 days.
Given
numbers x_1...x_n
, on which days should Bob perform missions, and on which days should he rest, in order to make as much money as possible and not work more than 5 days? Your solution should be O(n)
My issue:
I am having trouble coming up with the recurrence for this problem. I have been thinking about this problem for a long time. My original thought was to let p[i] = max{x_i + x_i-1 + .... + x_i-4}, where p[i] is the max profit earnable from days i-4 to i.
However, I realize, one, that this does take in to account that the optimal solution might have two consecutive work days, and two, I am not building off previous solutions.
My Question: Can anyone give me insight on understanding the structure of this problem? I feel like I am just not understanding the key properties that would make the solution easy to see.
Thanks in advance!