A parade organizer has lined up n numbered positions, 0 through n - 1, each displaying a decorative value; position i is worth value[i] points. Some positions currently hold a lit torch and the rest are empty, given as a pattern string of '0' (empty) and '1' (lit) characters.
The crew may repeatedly perform this move: if position i is empty and the very next position i + 1 holds a lit torch, they may swap the two, so the torch advances one step toward the front of the line (to the lower-indexed position) and position i + 1 becomes empty. This move can be applied any number of times, in any order, to any pair of adjacent positions that currently match the empty-then-lit pattern — torches may never move backward, and two torches can never cross each other.
Your score is the sum of value[i] over every position i that ends up holding a lit torch. Determine the maximum score achievable after performing any sequence of these moves.
A single integer: the maximum score achievable.
Example 1
Input
5 4 1 7 2 9 01010
Expected
11
Explanation
Torches start at positions 1 and 3 (values 1 and 2). Advance the torch at position 1 to position 0 (value 4), and advance the torch at position 3 through the now-empty position 2 to land on position 2 (value 7) — it cannot advance further because position 1 is already occupied by the other torch. The torches now sit at positions 0 and 2, scoring 4 + 7 = 11, which is optimal.
Example 2
Input
6 3 8 1 2 9 4 100100
Expected
11
Explanation
Torches start at positions 0 and 3. The torch at position 0 is already at the front and cannot move further left. The torch at position 3 can advance through positions 2 and 1 (both empty) but not past position 0's torch, so its best stop is position 1 (value 8) rather than staying at position 3 (value 2) or stopping at position 2 (value 1). Final torch positions are 0 and 1, scoring 3 + 8 = 11.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →