[LeetCode] 53 - Maximum Subarray

문제

• 링크: https://leetcode.com/problems/maximum-subarray
• 난이도: Medium
• 태그: 배열, 다이내믹 프로그래밍
• 결과: Time: 0 ms (100%), Space: 71.76 MB (51.84%)

풀이

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur = 0;
        int ans = -1e5;
        for (int n : nums)
        {
            if (cur < 0)
            {
                cur = 0;
            }
        
            cur += n;
            ans = max(cur, ans);
        }

        return ans;
    }
};

어려웠다. 그런데 답을 알고나니 굉장히 간단한 논리였다! 이전까지의 합이 음수면 무조건 나부터 시작하는게 이득이라는 것이다.

음, 이걸 어려워했다니. 논리력에 대한 반성(?)을 해야겠다.

이 포스트는 달레 스터디(3주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.