All problems

Orchard Harvest Route

Hard · dynamic programming

An orchard is a grid of trees with m rows and n columns. grid[r][c] is what the tree in row r and column c is worth: positive for ripe fruit, negative for rotten fruit that costs you to clear away.

A picker works through the rows from top to bottom, one row at a time. In each row they:

  1. enter the row at some tree,
  2. walk along the row to the left or to the right, or stay where they are, and stop at a tree,
  3. pick every tree they stood on, including the first and the last, and add its value once.

Then they drop straight down from the tree where they stopped and enter the next row at the tree directly below.

In the first row the picker may enter at any column. In the last row they may stop at any column. Every row must be worked.

Return the largest total value the picker can collect.

Examples

Example 1

Input: grid = [[3, -2, 4], [-1, 5, -6]]

Output: 9

Start row 0 at column 2 and walk left to column 0: 4 - 2 + 3 = 5. Move down to column 0 of row 1 and walk right to column 1: -1 + 5 = 4. The total is 9.

Example 2

Input: grid = [[-3, -1], [-2, -4]]

Output: -5

Every row must be worked, so some value is taken in each row. Taking -3 in row 0 and -2 below it is as good as it gets.

Example 3

Input: grid = [[2, -1, 3, -4, 1]]

Output: 4

There is a single row. The best walk is from the first tree to the third: 2 - 1 + 3.

Constraints