The lantern wire

A wire of paper lanterns goes dark one lantern at a time, and each switch-off pays according to the two lanterns still lit beside it. What to remove first is the wrong question.

The problem

A wire across the market square carries n paper lanterns, lantern i burning at brightness glow[i]. At closing time the crew switches them off one at a time, in any order, until the wire is dark.

A photographer pays for every switch-off: the tip is the brightness of the nearest lantern still lit to the left, times the brightness of the lantern going dark, times the brightness of the nearest one still lit to the right. Where no lit lantern remains on a side, the wall bracket at that end stands in with a brightness of 1; brackets are never switched off. A dark lantern leaves the wire for good, so its neighbours become neighbours of each other and the next tip is read off the shortened wire.

Return the largest total tip the crew can collect.

Input. glow — a list of integers, the brightness of each lantern from left to right.

Output. An integer, the maximum total tip.

Example.

glow = [2, 4, 3, 5]   ->  115

Take the 3 first, between 4 and 5: 4·3·5 = 60. Then the 4, now between 2 and 5: 40. Then the 2, with only the bracket on its left: 10. The 5 last, alone: 5. Total 115. Always taking the dimmest first pays 93.

A second example, where a lantern worth nothing is worth removing early:

glow = [5, 0, 4]   ->  25

Switching off the 0 earns nothing, but it makes 5 and 4 neighbours: the 4 then pays 20 and the 5 pays 5. Leaving it for last caps the run at 24.

Constraints.

• 0 <= len(glow) <= 300
• 0 <= glow[i] <= 100
• The wire may be empty; the answer is then 0.

Hints

Approach

Brute force

Try every order: n! sequences, each O(n) to score. At n = 12 that is 5.7 billion steps, and the limit is 300.

The insight

Split a stretch on the lantern switched off last, not first — when the last one goes, its lit neighbours are exactly the two lanterns bounding the stretch, whatever happened inside it.

That pins the final tip at glow[i] * glow[k] * glow[j], fixed by the stretch alone. The lanterns left of k and those right of k are then closed sub-problems of the same shape, because k stays lit while both are cleared, so neither side can see across it. Splitting on the first removal gives no such guarantee, which is why it fails.

Algorithm

1. Build wire = [1] + glow + [1], so 0 and n+1 are the brackets.
2. Let best[i][j] be the most tips from clearing everything strictly between i and j, both still lit; a gap under 2 is worth 0.
3. Fill by increasing gap j - i, from 2 up to n + 1.
4. For each (i, j) try every k between them as the last one off: best[i][k] + wire[i]*wire[k]*wire[j] + best[k][j], keeping the maximum.
5. The answer is best[0][n + 1].

Complexity

Time O(n³) — about n²/2 stretches, each trying up to n split points, so roughly 4.5 million updates at n = 300. Space O(n²) for the table.

Solution

"""Lantern wire — interval DP on the lantern that is switched off last."""


def solve(glow):
    # Pad both ends with a brightness of 1: the wall brackets are never switched
    # off, so they can stand in for "no lit lantern on that side".
    wire = [1] + list(glow) + [1]
    n = len(wire)

    # best[i][j]: most tips earned by switching off every lantern strictly
    # between positions i and j, while i and j are still lit.
    best = [[0] * n for _ in range(n)]

    for span in range(2, n):                 # widen the gap: shorter runs are already solved
        for i in range(n - span):
            j = i + span
            top = 0
            for k in range(i + 1, j):
                # k is the LAST lantern off inside (i, j), so at that moment its
                # lit neighbours are exactly i and j, whatever happened before.
                tips = best[i][k] + wire[i] * wire[k] * wire[j] + best[k][j]
                if tips > top:
                    top = tips
            best[i][j] = top

    return best[0][n - 1]

TESTS = [
    (([2, 4, 3, 5],), 115),
    (([5, 0, 4],), 25),
    (([6, 2],), 18),
    (([7],), 7),
    (([3, 3, 3],), 39),
    (([1, 9, 2, 8, 1],), 243),
    (([],), 0),
]

Pitfalls

• Splitting on the first lantern switched off. It looks symmetric and is not: the two sides can still become neighbours, so the sub-problems overlap and the recurrence charges tips the wire never paid.
• Filling the table in plain row order. best[i][j] reads best[i][k] and best[k][j], both shorter stretches, so the loop has to widen the gap; a for i: for j: sweep reads zeros that are not filled yet and under-reports.
• Treating a zero-brightness lantern as skippable. It earns nothing itself, but removing it early joins two bright neighbours, which is worth real money.

Variants

• Cutting the parcel spur — also asks where to split, but on a tree, where one sweep suffices because the two pieces never interact.
• The fly cue sheet — a grid DP whose state is a row layout rather than an interval.