Stone Game V

Cutting the Crate Row

Tracked in this browser only

The statement here is our own: the same inputs, outputs and technique.

A row of crates stands on a dock. weight[i] is the weight of the crate in position i, counting from the left end of the row.

While the row holds more than one crate, you do this:

choose a cut point, which splits the row into a left part and a right part, both non-empty runs of neighbouring crates;
the part with the larger total weight is craned off the dock and is gone; the other part becomes the new row, and you bank points equal to that part's total weight;
if the two parts have the same total weight, you choose which of them is craned off; the part you keep becomes the new row and you bank its total weight.

The work finishes when one crate is left. Return the greatest number of points you can bank.

Examples

Example 1

Input: weight = [3, 1, 2]
Output: 4

Cut after the first crate. The left part weighs 3 and the right part weighs 3, so the choice is yours: crane off the left part, bank 3, and the row becomes [1, 2]. Cut that in the middle; the right part weighs 2 and goes, so bank 1 and one crate is left. That run banks 4.

Example 2

Input: weight = [6, 9]
Output: 6

The row admits one cut, giving parts of weight 6 and 9. The heavier part is craned off, so 6 is banked and a single crate is left.

Example 3

Input: weight = [5, 5, 5, 5]
Output: 15

Cut in the middle: both parts weigh 10, so crane one off and bank 10, leaving a row of two crates. Cut that in the middle too: both parts weigh 5, so bank 5 and one crate is left. That run banks 15.

Constraints

1 <= weight.length <= 500
1 <= weight[i] <= 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python

def best_banked_weight(weight: list[int]) -> int:

Java

public int bestBankedWeight(int[] weight)

Stone Game V

Examples

Constraints

The signature

How this problem was checked

More on the same topics