GessaGessa - 5 months ago 15x

Python Question

**The problem:**

There is a set of n days that Bob is planning to work, and on each day

`i`

`i`

`x_i`

`Given`

`x_1...x_n`

`O(n)`

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.`

Thanks in advance!

Answer

I really am grateful for all the solutions posted here. I was able to come up with the solution, so I thought I would post it. Note that this solution only returns the maximum profit, not any specific days.

`Let P[i] = the maximum expected profit from day 1...i if Bob rests on day i`

`Recurrence: P[i] = max{p[j] + x_j+1 + x_j+2 + ... + x_i-1, for i - 6 <= j < i`

Thus, we want `P[i]`

to be the sum of the last five consecutive days that bob would have worked if he rests on day `i`

, plus the profit he would have made by the last rest day `j`

**Code:**

```
def get_best_missions(x):
n = len(x)
p = [0 for i in range(n)]
for i in range(1,n):
j = i - 6
if j < 0:
p[i] = sum(x[0:i])
else:
p[i] = max(p[i], p[j] + x[j+1] + x[j+2] + x[j+3] + x[j+4] + x[i - 1])
return max(p)
```

**Example & Results**

```
x = [10, 10, 10, 5, 20, 10, 5]
best = get_best_missions(x)
p = [0, 10, 20, 30, 35, 55, 55]
best = 55
```

Source (Stackoverflow)

Comments