Starting Health With a Shield

Medium

A hero goes through a dungeon of n rooms, strictly in order. In room i the hero loses hits[i] health. The hero carries a shield that can be raised at most once, in any single room. In that room it absorbs up to shield damage, and the hero takes the rest as usual. The hero's health must stay strictly above zero the whole time. Return the smallest starting health that gets the hero through every room.

Example 1

hits=[4, 1, 9, 2], shield=6 → 11

The shield is best used in the third room, where it absorbs 6 of the 9 damage. You lose 4 + 1 + 3 + 2 = 10 in total and must keep at least 1, so you need 11.

Example 2

hits=[5, 5], shield=20 → 6

The shield fully blocks one room, leaving 5 damage, so you need 6 health.

Example 3

hits=[0, 0, 0], shield=0 → 1

Constraints

n == len(hits)
1 ≤ n ≤ 10⁵
0 ≤ hits[i] ≤ 10⁵
0 ≤ shield ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array

Similar problems

Two Boards Holding Water Medium Fewest Jumps to the End Medium Reach the Last Cell Medium As Many Trades as You Like Medium Where to Start the Lap Medium

Input

hits=[4, 1, 9, 2], shield=6

Expected

Run checks the first 3 tests in your browser. Submit checks all 97 tests on the server, hidden ones included.