[LeetCode] 1413. Minimum Value to Get Positive Step by Step Sum

https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/

Minimum Value to Get Positive Step by Step Sum - LeetCode

1413. Minimum Value to Get Positive Step by Step Sum - Easy

 

초기 시작 값 startValue를 양수로 정해놓는다.

그리고 이 값에 배열에 있는 수를 계속해서 더해 나가는데,

이 과정 중 값이 1미만이 되면 안되게하려면 초기 시작 값은 최소한 몇으로 세팅해야하는지 구하는 문제다.

 

초기 시작 값을 0 으로 잡고 쭉 더해나가자.

[-3, 2, -3, 4, 2] => [-3, -1, -4, 0, 2]

더해나가는 수 중, 최소값을 저장해놓자. => -4

이 최소값이 1이상이 되면 되므로, 0에서 5를 더한수를 초기값으로 잡으면 된다.

만약 이 값이 0보다 크다면 양수중 최소값인 1을 리턴해주자.

 

전체 풀이 코드

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int s = 0, m = INT_MAX;
        for (int num:nums) s+=num, m = min(m,s);
        return m<=0?-m+1:1;
    }
};