LeetCode 53. Maximum Subarray

문제

Related Topics: Array, Divide and Conquer, Dynamic Programming

연속되는 요소의 가장 큰 합을 구하면 된다.

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

풀이 방법

디스커션의 이 풀이를 보고 풀었다.

index 0번부터 끝까지 각 노드를 탐색하면서 sum을 기록한다.
sum이 음수가 되면 더이상 추적하지 않고 sum을 0으로 만든다. 왜냐하면 0은 명백하게 음수보다 큰 수이기 때문이다.

예를들면 다음과 같다.

arr: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
i=0  => sum = 0 + (-2) = -2,                 max = -2
        sum이 음수이므로 sum을 다시 0으로 만든다. 
        sum = 0
i=1  => sum = 0 + 1 = 1,                     max = 1
i=2  => sum = 1 + (-3) = -2,                 max = 1
        sum < 0 이므로, sum = 0
i=3  => sum = 0 + 4 = 4                      max = 4
i=4  => sum = 4 + (-1) = 3                   max = 4
i=5  => sum = 3 + 2 = 5                      max = 5
i=6  => sum = 5 + 1 = 6                      max = 6
i=7  => sum = 6 + (-5) = 1                   max = 6
i=8  => sum = 1 + 4 = 5                      max = 6

코드

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

시간복잡도 : O(N)