Max Score of an Alternating Left-Right Walk Over a Row of Signed Cells

A row of `n` cells holds integer values, some of which may be negative. A token starts on the leftmost cell with a score of `0`. You make at most `k` moves. The first move goes to the right, the second to the left, the third to the right, and so on, alternating. A move may cover any number of cells in its direction, including zero. Each move adds to the score the sum of the values of every cell from the move's starting cell to its ending cell, both included. The score must never be negative: a move that would leave the score below `0` is not allowed. Return the highest score you can have after at most `k` moves. ### Function Signature ```python def max_row_walk_score(board: list[int], k: int) -> int: ``` ### Rules - Cells are indexed `0` to `n - 1` from left to right, and the token starts on cell `0`. - Move number `t`, counting from `1`, is a right move when `t` is odd and a left move when `t` is even. A right move from cell `p` ends on any cell `q` with `p <= q <= n - 1`; a left move from cell `p` ends on any cell `q` with `0 <= q <= p`. - A move from `p` to `q` adds `board[min(p, q)] + ... + board[max(p, q)]` to the score. A move that ends where it starts (`q = p`) therefore adds `board[p]`. - After every move the score must be at least `0`. The check is made once per move, on the score after the whole move, not cell by cell during it. - The direction of each move is fixed by its number: to move right again after a right move, you first have to make a left move, which may be a zero-length move if the score allows it. - You may stop after any number of moves from `0` to `k`. Making no moves leaves the score at `0`, so the answer is never negative. ### Constraints - `1 <= len(board) <= 50` - `-4 * 10^5 <= board[i] <= 4 * 10^5` - `1 <= k <= 4 * 10^8` - The answer can exceed `2^31 - 1` (it can reach `8 * 10^15`); use 64-bit integers in typed languages. - The original take-home allowed cell values up to `4 * 10^8` in absolute value, which pushes the best score toward `8 * 10^18` and makes 64-bit overflow a real concern. This version caps `|board[i]|` at `4 * 10^5` so every answer stays below `2^53`; `k` keeps its original bound. ### Examples **Example 1** ```text Input: board = [-2, 5, -1, 3], k = 3 Output: 19 ``` Move 1 goes right from cell `0` to cell `3` and adds `-2 + 5 - 1 + 3 = 5`. Move 2 goes left from cell `3` to cell `1` and adds `5 - 1 + 3 = 7`, for a score of `12`. Move 3 goes right from cell `1` to cell `3` and adds `7` again, for `19`. **Example 2** ```text Input: board = [1, -8, 6], k = 1000000 Output: 5999983 ``` A first move to cell `2` would add `1 - 8 + 6 = -1` to a score of `0`, which is not allowed, and a move to cell `1` would add `-7`. So moves 1 and 2 stay on cell `0` and add `1` each. With a score of `2`, move 3 goes right to cell `2` and adds `-1`, leaving `1`. Every later move stays on cell `2` and adds `6`, giving `1 + 6 * 999997 = 5999983`. **Example 3** ```text Input: board = [-5, 4], k = 10 Output: 0 ``` The first move starts on cell `0` and adds either `-5` (staying) or `-5 + 4 = -1` (moving to cell `1`). Both would make the score negative, so no move can be made and the score stays `0`.