Two Harvesters Down the Orchard

Hard

An orchard is given as a matrix orchard with rows rows and cols columns: orchard[i][j] is the number of apples that can be gathered in cell (i, j). Two harvesters stand in the top row: the first in the left corner (0, 0), the second in the right corner (0, cols - 1). On each move a harvester goes down one row, from (i, j) to (i + 1, j - 1), (i + 1, j) or (i + 1, j + 1), without leaving the orchard. Both move at the same time until they reach the bottom row. A harvester gathers all the apples in every cell it passes, including its starting cell. If both harvesters end up in the same cell, its apples count only once. Return the largest total number of apples the two harvesters can gather.

Example 1

orchard=[[2, 0, 4], [1, 6, 0], [3, 0, 5]] → 21

The left harvester goes 2 → 1 → 3 and the right one goes 4 → 6 → 5: 6 + 15 = 21. Had both passed through the 6, it would have counted only once.

Example 2

orchard=[[1, 1], [0, 9], [7, 0]] → 18

In the second row the right harvester takes the 9, in the third the left one takes the 7: 1 + 1 + 9 + 7 = 18.

Constraints

2 ≤ rows, cols ≤ 70
rows = len(orchard), cols = len(orchard[i])
0 ≤ orchard[i][j] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Matrix