FunctionRacerProblemsRace

Harvest With a Rest Gap

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

A row of fruit trees is described by yields, where yields[i] is how much fruit tree i gives when you pick it. Picking tires you out: after picking tree i you must leave the next gap trees alone, so the next tree you pick must have an index of at least i + gap + 1. You may pick any number of trees, including none, which gives a total of 0. Return the largest total yield you can collect. With gap = 0 you can pick every tree, and with gap = 1 no two neighbors can both be picked.

Example 1

yields [3,10,4,7]
gap 1
returns 17

Trees 1 and 3 give 10 + 7 = 17, the best total with no two neighbors picked.

Example 2

yields [6,5,6,5,6]
gap 2
returns 12

After tree 0 the next pick must be tree 3 or later, so trees 0 and 4 give 6 + 6 = 12.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems