0815HardArrayMathDynamic ProgrammingGame Theory

Cutting the Crate Row

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

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

Java

public int bestBankedWeight(int[] weight)

The intended approach

Time O(n^2) for n crates.Space O(n^2) for the run values and the two running-maximum tables.

Every row that can ever appear is a run of neighbouring crates, so runs are settled from the shortest upwards with prefix sums giving any run's weight. Within one run the left part's weight only grows as the cut point moves right, which splits the cut points into the block where the left part is lighter, at most one balanced cut, and the block where the right part is lighter; a pointer that only ever moves forward locates that boundary for each run. Two running maxima, the best value of keeping a left part from a fixed starting crate and the best value of keeping a right part up to a fixed ending crate, reduce each block to a single lookup, and the balanced cut is tried both ways.

Pythonentry point: best_banked_weight

def best_banked_weight(weight):
    # Interval work: settle every run of crates from the shortest run upwards.
    # For a run, the cut positions fall into three groups because the left total
    # only grows as the cut moves right: cuts where the left side is lighter,
    # at most one cut where the two sides balance, and cuts where the right side
    # is lighter. A monotone pointer finds the balance point for each run, and
    # two running maxima -- the best value of keeping a left part that starts at
    # a fixed crate, and the best value of keeping a right part that ends at a
    # fixed crate -- turn each group into one lookup.
    #
    # Time: O(n^2), since the pointer moves forward only.
    # Space: O(n^2) for the three tables.
    n = len(weight)
    if n == 1:
        return 0
    pre = [0] * (n + 1)
    for i, w in enumerate(weight):
        pre[i + 1] = pre[i] + w
    NONE = -1
    dp = [0] * (n * n)
    keep_left = [NONE] * (n * n)
    keep_right = [NONE] * (n * n)
    for l in range(n - 1, -1, -1):
        base = l * n
        t = l
        for r in range(l, n):
            total = pre[r + 1] - pre[l]
            if r == l:
                val = 0
            else:
                while 2 * (pre[t + 1] - pre[l]) < total:
                    t += 1
                val = 0
                if t - 1 >= l:
                    got = keep_left[base + t - 1]
                    if got > val:
                        val = got
                if 2 * (pre[t + 1] - pre[l]) == total:
                    if t <= r - 1:
                        left_val = (pre[t + 1] - pre[l]) + dp[base + t]
                        if left_val > val:
                            val = left_val
                        right_val = (pre[r + 1] - pre[t + 1]) + dp[(t + 1) * n + r]
                        if right_val > val:
                            val = right_val
                    nxt = t + 1
                else:
                    nxt = t
                if nxt <= r - 1:
                    got = keep_right[(nxt + 1) * n + r]
                    if got > val:
                        val = got
            dp[base + r] = val
            mine = total + val
            prev = keep_left[base + r - 1] if r > l else NONE
            keep_left[base + r] = mine if mine > prev else prev
            other = keep_right[base + n + r] if l + 1 <= r else NONE
            keep_right[base + r] = mine if mine > other else other
    return dp[n - 1]

The obvious version

Follow the rules literally: for the row in hand, try every cut point, keep whichever part the rules leave behind, and recurse on it, taking the best result. No table and no reuse, so it is only usable on short rows.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_banked_weight(weight):
    """Try every cut of every row that can arise, with no table at all."""
    def go(part):
        if len(part) == 1:
            return 0
        best = 0
        for k in range(1, len(part)):
            left = part[:k]
            right = part[k:]
            ls = sum(left)
            rs = sum(right)
            if ls < rs:
                cand = ls + go(left)
            elif rs < ls:
                cand = rs + go(right)
            else:
                a = ls + go(left)
                b = rs + go(right)
                cand = a if a > b else b
            if cand > best:
                best = cand
        return best

    return go(list(weight))

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in