i carries the number stones[i]. A frog starts on stone 0 and has to reach the last one. It may only jump forward, from stone i to any stone j > i, and such a jump earns (j - i) · stones[j] points: the jump length times the number on the stone it lands on.
Return the largest total score the frog can collect on its way to the last stone.
There can be up to 10⁵ stones, so trying every "from, to" pair in O(n²) is too slow. Aim for linear time.stones=[2, 6, 3, 5] → 16
The best route is 0 → 1 → 3: 1 · 6 + 2 · 5 = 16. Jumping straight 0 → 3, for example, gives only 3 · 5 = 15.
stones=[9, 1, 1] → 2
The first stone's value never counts. Both routes, 0 → 2 and 0 → 1 → 2, score 2.
stones=[2, 6, 3, 5]
16
Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.