최대 연속 부분 수열의 합

(아래 쪽에 update 있음)

 

왜 이 문제는 볼 때마다 새로운걸까?

이 영상만 네 다섯 번은 본 것 같다.

 

https://youtu.be/OxsZKLfaWX0

 

컨셉은:

"수의 합을 반복적으로 구하는데, 합이 음수면 0으로 초기화하고 다음 수부터 다시 시작한다."

 

합이 음수일 때 0으로 초기화하는 것은,

전체 배열 중 양수 최소 하나 이상 있다고 가정하기 때문이다.

양수가 최소 하나 이상 있다면 그 양수 하나만 가지는 게 (음수 합보다) 이득이다.

 

그래서 또 이 알고리즘에 빈틈이 생기는데,

배열의 모든 수가 음수인 경우에 0을 반환하게 된다는 것이다.

그래서 이 경우는 배열에 있는 수 중 가장 큰 (음)수를 반환한다.

 

물론 0을 반환할 때 항상 배열의 모든 수가 음수인 것은 아니다.

배열의 모든 수가 0일 때, 혹은 0과 음수로만 이루어진 경우에도 0을 반환한다.

하지만 이 경우도 배열에 있는 수 중 가장 큰 수를 반환하는 알고리즘이 적용되어도 괜찮다.

 

출처는 사진 아래 링크랑 내 생각

 

-- update --

위 방법에서 합이 음수일 때 0으로 초기화하는 것은

현재까지의 합에 현재 수를 더하는 것이 이득인지 vs 그냥 현재 수 단독으로 새로운 부분 배열을 시작하는 것이 이득인지

를 판단하는 것이다.

 

따라서 아래와 같이도 짤 수 있으며

아래와 같이 짤 경우 배열의 모든 수가 음수여도 다시 가장 큰 수를 찾지 않아도 된다.

int maxSubArray(vector<int>& nums) {
    int tmp = 0, maxv = INT_MIN;
    
    for(int i=0; i<nums.size(); i++){
        tmp += nums[i];
        tmp = max(tmp, nums[i]);
        maxv = max(tmp, maxv);
    }
    
    return maxv;
}

 

https://leetcode.com/problems/maximum-subarray/discuss/343771/cpp-faster-than-98 참고