LeetCode 53 - Maximum Subarray

https://leetcode.com/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-interview-150

 

가장 합이 큰 subarray를 찾아라.

 

subarray를 찾아야 하기 때문에 정렬은 안된다.

가장 단순한 방법은 모든 가능한 부분 배열을 탐색하는 것이다. 물론 이는 배열의 길이가 늘어날수록 아주 비효율적인 알고리즘이 된다.

합을 어떻게 크게 만들 수 있을까. 합은 양수를 더하면 증가하고 음수를 더하면 감소한다.

특정 범위의 합이 음수라면 다음 숫자를 더하는 것 보다 다음 숫자부터 다시 시작하는 것이 맞다는 소리다.

투포인터를 이용하겠다. left,right를 0으로 두고 right로 범위를 확장시켜 나간다.

확장시키면서 최대 합을 갱신한다.

그러다가 합이 음수가 되는 순간 시작점인 left를 변경해 다시 검사를 하는 방식을 사용하겠다.

이 문제에서는 subarray의 범위를 구할 필요는 없어 left를 관리할 필요는 없다.

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = 0;

        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            maxSum = Math.max(maxSum, currentSum);

            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        return maxSum;
    }
}

 

그런데 이 문제의 분류를 보니 카데인 알고리즘이라는 내용이 나왔다.

카데인 알고리즘이 뭘까?

카데인 알고리즘은 1차원 배열에서 최대 부분 배열 합을 O(n) 시간 복잡도로 찾는 알고리즘이다.

동적 프로그래밍을 사용한다.

핵임 아이디어는 다음과 같다.

1. 배열을 순회하면서 각 위치에서 끝나는 최대 부분 배열의 합을 계산한다.
2. 각 단계에서 두 가지 선택 중 하나를 한다.
   1. 현재 원소부터 새로운 부분 배열을 시작한다.
   2. 현재 원소를 이전 부분 배열에 추가한다.
3. 이 선택은 현재까지의 합이 양수인가, 음수인가에 따라 결정된다.

설명을 보면 알 수 있듯이 이 문제 자체가 카데인 알고리즘이었다.

현재 위치에서 최대 부분합을 고려하는 부분이 핵심이다.

여기서도 나오는 핵심이 이전까지의 합이 음수이면 현재 요소부터 새로운 부분 배열을 시작하는 것이 이득이다.

class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

 

Divide and Conquer 방식을 사용해서 푸는 방법도 있다.

문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 해결한 다음 결과를 합쳐서 전체 문제의 해결책을 얻는 방법이다. 다음과 같은 과정을 거친다.

1. 배열을 두 부분으로 나눈다.
2. 왼쪽 절반의 최대 부분 배열을 찾는다.
3. 오른쪽 절반의 최대 부분 배열을 찾는다.
4. 중간을 가로지르는 최대 부분 배열을 찾는다.
5. 위의 세 경우 중 가장 큰 합을 반환한다.

핵심은 중간을 가로지르는 최대 부분 배열이다. 이는 다음과 같은 과정을 통한다.

1. 중간점에서 왼쪽으로 가며 최대 합을 찾는다.
2. 중간점에서 오른쪽으로 가며 최대 합을 찾는다.
3. 두 합을 더한다.

위의 과정들을 재귀를 통해 배열의 크기가 1이 될 때까지 반복하면 된다.

class Solution {
    public int maxSubArray(int[] nums) {
        return findMaxSubarray(nums, 0, nums.length - 1);
    }

    private int findMaxSubarray(int[] nums, int left, int right) {
        if (left == right) {
            // 배열 크기가 1
            return nums[left];
        }

        int mid = left + (right - left) / 2;

        int leftSum = findMaxSubarray(nums,left, mid);
        int rightSum = findMaxSubarray(nums, mid + 1, right);
        int crossSum = findMaxCrossingSubarray(nums, left, mid, right);

        return Math.max(Math.max(leftSum, rightSum), crossSum);
    }

    private int findMaxCrossingSubarray(int[] nums, int left, int mid, int right) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }

        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }

        return leftSum + rightSum;
    }
}