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

問題

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

解答と解説

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        minSum, curSum = float("inf"), 0
        for n in nums:
            curSum += n
            minSum = min(minSum, curSum)
        
        return 1 if minSum >= 0 else abs(minSum) + 1

numsの要素数をnとした時、

• Time Complexity: O(n)
• Space Complexity: O(1)

startValue = stepSumの最小値の絶対値 + 1と考えれば良い。stepSumの最小値が0以上であればstartValueの最小値は1になるのでその点は注意する。