MinHealthGame

https://leetcode.com/discuss/interview-question/1789737/amazon-OA

进阶班： https://app.gitbook.com/s/-M33ghpQv0ZbnP8UX-Qg/9.dynamic-programming/174.-dungeon-game-h Solution:

Intuition: Get the maximum answer possible i.e. sum of all elements now use the armor only for the maximum element because we want the answer to be minimum and also add + 1 to it because health at any stage cannot be 0. Logic for this is : Sum of all the elements - min(armor, maximum element)+1

public class MinHealth {
    public static void main(String[] args){
        MinHealth minHealth = new MinHealth();
        System.out.println(minHealth.findMinHealth(new int[]{1,1,1,1,1},5));
    }
    public int findMinHealth(int[] power, int armor){
        int maxPower = Integer.MIN_VALUE;
        int totalSum = 0;
        for(int p : power){
            totalSum+=p;
            maxPower = Math.max(maxPower,p);
        }
        return totalSum-Math.min(armor,maxPower)+1;
    }
}