FastPrep
Problem · Dynamic Programming

Maximum Remaining Drone Power

Learn this problem
● EasyAkuna Capital logoAkuna CapitalINTERNOA

Problem statement

You are given a 4 x 4 integer grid city, where city[i][j] is the power cost of passing through cell (i, j).

A delivery drone starts with 100 units of power and must travel from the top row to the bottom row under these rules:

  • It may start at any cell in the first row.
  • From cell (i, j), it may move only to an existing cell in the next row: (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
  • It must end in the last row.

Each time the drone passes through a cell, its power is reduced by that cell's cost. Return the maximum power remaining after the drone reaches the last row.

Note: The final power can be negative.

Function

maxPower(city: int[][]) → int

Examples

Example 1

city = [[10, 20, 30, 40], [60, 50, 20, 80], [10, 10, 10, 10], [60, 50, 60, 50]]return = 0

Two possible paths are:

  • (0, 0) -> (1, 1) -> (2, 2) -> (3, 3), which leaves 100 - 10 - 50 - 10 - 50 = -20 power.
  • (0, 1) -> (1, 2) -> (2, 2) -> (3, 2), which leaves 100 - 20 - 20 - 10 - 50 = 0 power.

The maximum possible remaining power is 0.

Example 2

city = [[4, 16, 14, 21], [17, 0, 5, 5], [4, 41, 22, 3], [2, 51, 6, 0]]return = 90

The path (0, 0) -> (1, 1) -> (2, 0) -> (3, 0) has total cost 4 + 0 + 4 + 2 = 10, leaving 100 - 10 = 90 power. No valid path has a lower total cost.

Constraints

  • city has exactly 4 rows and 4 columns.
  • 0 <= city[i][j] < 100

More Akuna Capital problems

drafts saved locally
public int maxPower(int[][] city) {
  // write your code here
}
city[[10, 20, 30, 40], [60, 50, 20, 80], [10, 10, 10, 10], [60, 50, 60, 50]]
expected0
checking account