LeetCode : 53. Maximum Subarray

사실 문제 유형은 DP(Dynamic Programming)으로 분류되어 있었지만, 그냥 구현? 문제로 풀었다.

아이디어는 문제의 Discuss 탭에 있는 외국인 분의 코드를 보고 얻었다...ㅎ

 

[메인 로직]

최대 합을 저장하는 변수 ans, 매 번 큰 값을 비교하여 저장하는 변수 sum을 두고 탐색하는 식으로 구현했다.

예를 들어, [-1, 2, 3]의 배열이 있는 경우

idx = 1 => -1+2 < 2 이기 때문에 계속 더하지 않고 자기 자신부터 다시 시작하는 것이 이득이다. 따라서, sum = 2가 된다.

idx = 2 => 2+3 > 3 이기 때문에 계속 더해주는 것이 이득이다. 따라서, sum = 5가 된다.

 

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