[LeetCode/easy] Maximum Subarray (C++)

leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

인접한 숫자의 누적합을 구해가며 최대값을 갱신합니다. 근데 이때 누적합이 음수가 된다면 여태까지의 누적합이 최대값이 될 수 없으므로, 0으로 바꿔주고 다시 누적 합을 구합니다. 마지막에 기록되어있는 누적합의 최대값이 답이 됩니다.

 

/* O(N) */

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

 

다음으로 분할 정복을 이용한 풀이입니다. 분할 정복에서는 부분 배열을 가능한 같은 크기의 두 부분 배열로 나누는 것이 좋기 때문에 시작 인덱스 start와 끝 인덱스 end를 이용하여 부분 수열의 중간값 mid를 찾아 두 부분 배열로 나눕니다. 이렇게 나눠진 부분 배열은 두가지 케이스를 가집니다.

 

1. 부분 배열이 왼쪽 부분 배열 혹은 오른쪽 부분 배열 하나에만 포함된다.

2. 부분 배열이 중간값에 걸쳐있다.

 

ex)

[3 4 5] | 1 -1 2

1 -1 -3 | [3 4 5]

-1 [3 4 | -5 9] -2

 

이러한 두가지 케이스를 고려하여, mid부터 시작해서 start까지, mid + 1부터 시작해서 end까지 최대 부분 배열을 찾아 두 부분 배열을 합친 값과 왼쪽 부분 배열을 계속 쪼개서 남은 수, 오른쪽 부분 배열을 계속 쪼개서 남은 수의 최대값을 비교하는 과정을 반복합니다.

 

/* Divide & Conquer : O(NlogN) */

class Solution {
public:
    int findCross(vector<int>& nums, int start, int mid, int end) {
        int leftMax = -2147000000, rightMax = -2147000000;
        
        int sum = 0;
        for(int i = mid; i >= 0; i--) {
            sum += nums[i];
            leftMax = max(leftMax, sum);
        }
        
        sum = 0;
        for(int i = mid + 1; i <= end; i++) {
            sum += nums[i];
            rightMax = max(rightMax, sum);
        }
        
        return leftMax + rightMax;
    }
    
    int DC(vector<int>& nums, int start, int end) {
        if(start == end) return nums[start]; // base case
        int mid = (start + end) / 2;
        
        int leftSum = DC(nums, start, mid);
        int rightSum = DC(nums, mid + 1, end);
        int crossSum = findCross(nums, start, mid, end);
        
        return max(leftSum, max(rightSum, crossSum));
        
    }
    
    int maxSubArray(vector<int>& nums) {
        return DC(nums, 0, nums.size() - 1);
    }
};