[Leetcode] 53. Maximum Subarray (C++)

문제

53. Maximum Subarray

코드

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0], curSum = 0;
        
        for(int i = 0; i < nums.size(); i++){
            curSum += nums[i];
            if(curSum > maxSum) maxSum = curSum;
            if(curSum < 0) curSum = 0;
        }
        return maxSum;
    }
};

접근

처음에는 당연히 모든 케이스를 살펴보는 O(N^2)의 풀이를 떠올랐다. 한 번의 스캔으로 답을 구할 수 있는 방법이 뭐가 있을까 생각해보다. 값들을 누적하면서 유지하는 최대 값과 비교하고 동시에 그 값이 음수라면 다시 0으로 설정한다. 이유는 후에 나오는 값들의 합이 음수라면 당연히 더 작아질 것이고 양수라면 현재 값이 음수라 결과적으로 더 작은 값이 되기 때문이다.