53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

이지인데 난 왜 헤메나;;

정수 목록이 주어졌을 때 합이 최대가 되는 부분 목록의 합을 구하는 문제다.

누적된 합보다 인수가 클 때 다시 누적을 시작한다.

금요일인데 억지로 하고 있어서 그런가... 방법과 로직은 이해가 되는데 서로 연결이 안된다..

왜 max 함수 내용으로 그것이 구현되는가... 후 다음에 다시 봐야겠다.

 

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int ret = nums[0];

        for (int i=1; i<nums.size(); ++i)
        {
            sum = max(nums[i], nums[i] + sum);
            if (ret < sum) {
                ret = sum;
            }
        }
        
        return ret;
    }
};