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

풀이

O(N)으로 푸는 법 보기 . return이 하나이고 코드가 간결하다.
내 방법도 나쁘지는 않은듯.

코드

C++ : 내가 짠 코드 O(NlgN)

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        for(int i = 1; i < nums.size(); i++)
            nums[i] += nums[i-1];
        sort(nums.begin(),nums.end());
        if(nums[0]<0) return -nums[0]+1;
        return 1;
    }
};

C++ : O(N)

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int sum = 0;
        int minSum = 0;
        for(int i = 0 ; i < nums.size(); i++){
            sum += nums[i];
            minSum = min(sum,minSum);
        }
        return 1 - minSum;
    }
};