Minimum Starting Health
MediumGreedy · Amazon
You play a game with n levels that must be completed in order. Completing level i costs damage[i] health.
You also have one piece of armor that you may use on at most one level. On that level it blocks up to armor damage, so you lose max(0, damage[i] - armor) health there instead.
Your health must stay strictly greater than 0 at every moment, including after the last level. Return the minimum starting health needed to complete all levels.
Example 1
- Input:
- damage = [5, 1, 9, 2], armor = 6
- Output:
- 12
- Explanation
- The levels deal 17 damage in total. Using the armor on the 9-damage level blocks the full 6, leaving 11 damage, so you need 12 health to stay above 0.
Example 2
- Input:
- damage = [3, 2, 4], armor = 10
- Output:
- 6
- Explanation
- The armor could block 10, but the biggest level only deals 4, so it saves 4. The remaining 5 damage requires 6 starting health.
Constraints
1 <= damage.length <= 10^50 <= damage[i] <= 10^50 <= armor <= 10^5