[leetcode] Minimum Value to Get Positive Step by Step Sum

문제

Given an array of integers nums, you start with an initial positive value startValue.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

문제 예시

Input: nums = [-3 , 2, -3, 4, 2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1 (see example below).

step by step sum

startValue = 4	startValue = 5	nums
(4 -3 ) = 1	(5 -3 ) = 2	-3
(1 +2 ) = 3	(2 +2 ) = 4	2
(3 -3 ) = 0	(4 -3 ) = 1	-3
(0 +4 ) = 4	(1 +4 ) = 5	4
(4 +2 ) = 6	(5 +2 ) = 7	2

Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.

Input: nums = [1,-2,-3]
Output: 5

제한사항

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

풀이 접근 방식

시간 및 공간 복잡도

소스코드

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
            
        sum = min_val = 0 
        for num in nums:
            sum += num
            min_val = min(min_val, sum)
        return -min_val + 1