FastPrep
Problem · Dynamic Programming

Timed Coin Collection in a 2×N Grid

Learn this problem
● HardAtlassian logoAtlassianFULLTIMEOA

Problem statement

Start at the top-left cell of a 2 by n grid at time zero. Move each second to an orthogonally adjacent unvisited cell until every cell has been visited exactly once. Visiting cell (r,c) at time t earns t * coins[r][c]. Return the maximum total.

Function

maxTimedCoins(coins: int[][]) → long

Examples

Example 1

coins = [[1,4,3,2],[2,1,3,2]]return = 77

An optimal route visits top-left, traverses the bottom row to the right, then returns along the top row.

Example 2

coins = [[1,3],[4,2]]return = 19

The route top-left, bottom-left, bottom-right, top-right earns 0+4+4+9.

Constraints

  • 1 <= n <= 100000
  • 1 <= coins[r][c] <= 100000

More Atlassian problems

drafts saved locally
public long maxTimedCoins(int[][] coins) {
  // Write your code here.
}
coins[[1,4,3,2],[2,1,3,2]]
expected77
checking account