Problem library

Shielded Run

Hard
dynamic programmingmatrix

A dungeon is a grid of integers: positive cells are loot, negative cells are traps that take loot away. You enter at the top-left cell and leave at the bottom-right cell, moving only right or down, and every cell you step on (including both ends) counts.

You carry one shield. You may use it on at most one trap cell on your path to count that cell as 0 instead. Return the largest total you can finish with. The grid has at least one cell.

Examples

Input: grid = [[1,-5,2],[3,-9,4],[-2,6,1]]
Output: 11
Input: grid = [[-7]]
Output: 0