FastPrepMaximum Profit With Value-Based Jumps

Maximum Profit With Value-Based Jumps

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

You start at index 0 of an array of positive integers profits. At an index i, choose exactly one action:

  • Take profits[i] profit and jump to index i + 1 + profits[i].
  • Skip the profit and move to index i + 1.

The process ends after moving beyond the last index. Return the maximum total profit you can collect.

Function

maximumJumpProfit(profits: int[]) → long

Examples

Example 1

profits = [3,2,5,1,4]return = 7

Take 3 at index zero, jump to index four, and take 4.

Example 2

profits = [1,1,1,1]return = 2

Taking a one skips the next index, so at most two values can be collected.

Example 3

profits = [5,1,1]return = 5

Taking the first value jumps beyond the array and is optimal.

Constraints

  • 1 <= profits.length <= 200000.
  • 1 <= profits[i] <= 10^9.
  • The answer fits in a signed 64-bit integer.

More Google problems

See Google hiring insights
public long maximumJumpProfit(int[] profits) {
    // Write your code here.
}
profits[3,2,5,1,4]
expected7
Checking account…