[ leetcode 문제풀이 ] Maximum Subarray

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

Maximum Subarray - LeetCode

(Maximum Subarray 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Maximum Subarray 문제 설명 >

 

Maximum Subarray 문제는 다음과 같다.

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

A subarray is a contiguous part of an array.

 

주어진 정수 배열 nums에 대해 가장 큰 합을 갖는 subarray를 찾고, 그 합을 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4 이다.

Follow up question: O(n) solution을 찾았다면, 분할 정복 방법으로 새로운 solution을 찾아보아라.

 

 

 

---

 < Maximum Subarray 문제 접근(1) >

 

subarray의 합을 찾는 것은 곧 배열의 구간 합을 탐색한다는 것이다. 따라서, prefix sum을 사용해 접근하는 것이 좋아보인다.

입력받은 nums 배열을 재정의해 nums[i]가 nums[0 ... i]까지의 합이라고 하자. 그러면 i원소부터 j원소까지의 합(i ≤ j)은

nums[j] - nums[i-1]로 O(1)의 복잡도로 계산할 수 있는 것이다.

 

그럼 이제 구간 합을 어떻게 탐색해야 할지 생각해보자. 간단하게 생각하면 nums의 원소 중 가장 큰 값에서 가장 작은 값을 뺀 것이 바로 maximum subarray의 합이 될 것이다. 단, 가장 작은 값의 index ≤ 가장 큰 값의 index를 만족해야 한다.

 

이렇게 하고 나니 전에 풀었던 "Best Time to Buy and Sell Stock" 과 같은 문제임을 알 수 있다.

[ leetcode 문제풀이 ] Best Time to Buy and Sell Stock

 

앞서 말한 원리로 구현한 코드는 다음과 같다. (Cpp 사용)

 

int maxSubArray(vector<int>& nums) {
    for(int i=1;i<nums.size();i++)
        nums[i]+= nums[i-1];		// prefix sum으로 nums 재정의
        
    int low = 0;			// i = 0 인 경우를 고려하기 위함
    int ans = nums[0];
    for(int i=0;i<nums.size();i++){
        ans = max(ans, nums[i]-low);
        low = min(low, nums[i]);
    }
    return ans;
}

 

nums[i ... j]의 합 = nums[j] = nums[i-1] 이므로 i=0인 경우에 대한 탐색도 진행할 수 있도록 nums[-1] = 0으로 low의 값을 초기화해준다. 출력하고자 하는 subarray의 합을 나타내는 ans는 0이 아닌 nums[0]으로 초기화해준다. 만약 nums의 모든 원소가 음수로 이루어진 경우 ans 값 업데이트 과정이 nums원소를 무시해버리기 때문이다. 그리고 i번째 원소를 subarray의 원소로 포함할 수 있도록 ans 값 업데이트 후 low 값 업데이트를 하도록 순서를 뒀다.(low 값 업데이트를 먼저 하게 되면 i번째 nums원소를 빼고 subarray 합을 계산하므로 nums[0]은 고려하지 않고 넘기게 되어버린다.)

 

이렇게 만든 알고리즘은 nums을 재정의하는 과정에서 O(n), ans와 low를 찾는 과정에서 O(n)으로 총 O(n)의 시간복잡도를 가짐을 알 수 있다. 

 

 

 

---

 < Maximum Subarray - Follow Up >

 

Divide&Conquer 방법으로 문제를 푸는 방법을 생각해보자. 우선 nums배열의 정 중앙의 원소 mid가 있을 때 maximum subarray가 있을 수 있는 위치는 nums[0 ... mid] 혹은 nums[mid+1 ... (end)] 혹은 mid를 중간에 포함한 어떤 배열 nums[left ... mid ... right]의 세 가지 경우가 있을 것이다. 처음 두 가지 경우는 탐색할 nums의 크기를 절반으로 줄여가며 재귀호출하면 되고, 세 번째 경우는 따로 계산해줘야 한다. 이를 위해 nums 배열에서 nums[0 ... i]에서 nums[i]를 반드시 포함하는 maximum subarray 값과 nums[i ... (end)]에서 nums[i]를 반드시 포함하는 maximum subarray 값을 미리 구해둔다.(prefix[i], suffix[i]) 그러면 세 번째 경우는 prifix[mid] + suffix[mid+1] (nums[0 ... mid] 중 nums[mid]를 포함하는 최대 값, nums[mid+1 ... (end)] 중 nums[mid+1]을 포함하는 최대 값)으로 계산해줄 수 있다. (prefix와 suffix은 연속된 subarray이므로 전체가 subarray를 만족)

 

이를 코드로 나타내면 다음과 같다. (Cpp 사용)

 

vector<int> prefix, suffix;
int maxSubArray(vector<int>& nums) {
    prefix = suffix = nums;
    for(int i=1;i<nums.size();i++)
        prefix[i] += max(0, prefix[i-1]);
    for(int i = nums.size()-2;i>-1;i--)
        suffix[i] += max(0, suffix[i+1]);
        
    return maxDivConquer(nums, 0, nums.size()-1);
}
int maxDivConquer(vector<int>& nums, int left, int right){
    if(left == right) return nums[left];
    int mid = (left + right)/2;
    return max({maxDivConquer(nums, left, mid), maxDivConquer(nums, mid+1, right), 
        prefix[mid] + suffix[mid+1]});
}

 

굳이 divide&conquer 방법으로 풀이하라 해서 코드를 작성했지만 mid를 포함하는 subarray(세 번째 경우)를 고려하는 것이 별로 깔끔하게 처리되지 않았다. 어차피 prefix와 suffix를 계산해야할 거면 Kadane's Algorithm을 쓰는 것이 훨씬 나은듯 하다. 안해도 되는 일을 두 번 하는 느낌이기 때문이다.

 

(↓ 참고 - Kadane's Algorithm: maximum subarray solution으로 유명한 알고리즘)

int maxSubArray(vector<int>& nums) {
    int curMax = 0, maxTillNow = INT_MIN;
    for(auto c : nums)
        curMax = max(c, curMax + c),
        maxTillNow = max(maxTillNow, curMax);
    return maxTillNow;
}