[자바] 부분 배열의 합 중 가장 큰 값 구하기 (분할 정복 알고리즘)

위와 같은 배열이 있을 때, 부분 배열이 만들어지는 경우의 수는 빨간네모와 같은 영역을 가질 것이다.

우리는 이 문제의 해답을 분할 정복 알고리즘을 통해 구할것이다.

 

먼저 배열을 반으로 가르고 왼쪽, 오른쪽에서 각각 최대의 합을 갖는 부분 배열의 조각을 얻을 것이다.

여기서 구해지는 부분 배열은 처음에 잘랐던 중앙을 넘지 않는다.

 

그리고 마지막으로 전체 배열에서 중앙부터 좌,우로 뻗어나가며 가장 큰 합을 갖는 배열 조각을 얻을것이다.

이렇게 구한 배열 조각 중 가장 큰 합을 갖는 조각이 우리가 찾고자 하는 부분 배열이다.

 

이 방법은 재귀함수를 필요로 하는 만큼 코드를 이해하는 데 다소 어려울 수 있으니 그림으로 좀 더 살펴보고

짧은 코드와 주석으로 마무리하겠다.

 

 

1. LEFT

반의 반으로 배열을 쪼개면서 재귀함수를 돌다보면 우리는 {20, 0, -15} 만큼의 부분배열을 만날것이다.

이 배열이 만들 수 있는 가장 큰 부분배열은 20이다.

 

 

 

 

{4, -1} 배열에서 가장 큰 부분배열 값은 4다.

 

 

 

위 두 배열을 합했을때 가장 큰 부분배열 값은 20이다.

 

 

 

 

2. RIGHT

 

{5, 1, -3} 배열에서 가장 큰 부분배열 값은 6이고, 마지막 남은 부분배열은 8이다.

 

 

 

위 두 배열을 합했을 때 가장 큰 부분배열 값 11이다.

 

 

---

 

우리는 처음 배열에서 반으로 잘라 좌, 우로 나눠가며 가질 수 있는 가장 큰 부분배열 조각들을 구했다.

이제 정답은 두 가지 중 하나다.

1. 좌, 우의 부분배열 값중 가장 큰 20.

2. 중앙에서 이어진 부분배열.

 

1번은 구했으니 2번을 구할 필요가 있다.

 

처음 언급했듯이 좌, 우로 뻗어나가며 중앙과 이어진 가장 큰 부분배열 값을 양쪽에서 찾고 그 값을 서로 더할 것이다.

중앙부터 왼쪽으로 가장 큰 합은 8이고 오른쪽에서 가장 큰 값은 11이다.

공교롭게도 중앙에서 양쪽으로 뻗어나간 부분배열중 가장 큰 합을 갖는 배열은 전체배열 된다.

두 값을 더하면 19로써, 위에서 구했던 가장 큰 부분배열 조각인 20보다 작다.

따라서, 이 배열에서 가장 큰 합을 갖는 부분배열은 LEFT에서 구했던 {20, 0} 혹은 {20}이다.

 

지금까지 그림을 통해 알아본 과정을 코드로 보자.

public class divArrPractice {
    public static int solution(int[] nums) {
    
        return divideArray(nums, 0, nums.length - 1);
    }

    public static int divideArray (int[] nums, int left, int right) { // 반의 반으로 계속 쪼개기 위한 함수
        if (left == right) {
            return nums[left];
        }

        int mid = left + (right - left) / 2; // left+right로 발생할 수 있는 오버플로우를 방지한다.
        int maxLeft = divideArray(nums, left, mid);
        int maxRight = divideArray(nums, mid+1, right);
        int maxArr = getMaxArray(nums, left, mid, right);

        return Math.max(maxLeft, Math.max(maxRight, maxArr));
        // 최종적으로 left의 부분배열/right의 부분배열/중앙부터 양쪽으로 뻗어나가는 부분배열중 최댓값을 출력한다.
    }
    public static int getMaxArray(int[] nums, int left, int mid,  int right) {
    // left와 right에서 각각의 부분배열 합중 최댓값을 구한다. (처음 배열의 중앙을 넘지 않고)
    // 양쪽 모두에서 부분배열 최댓값을 구했다면, 마지막에 전체 배열의 중앙부터 뻗어나가며 최댓값을 구한다.
        int sumLeft = 0;
        int maxLeft = Integer.MIN_VALUE;

        for (int i = mid; i >= left; i--) {
            sumLeft += nums[i];
            maxLeft = Math.max(maxLeft, sumLeft);
        }

        int sumRight = 0;
        int maxRight = Integer.MIN_VALUE;

        for (int i = mid + 1; i <= right; i++) {
            sumRight += nums[i];
            maxRight = Math.max(maxRight, sumRight);
        }

        return maxLeft + maxRight;
    }
    
    public static void main(String[] args) {
        int[] nums = {20, 0, -15, 4, -1, 5, 1, -3, 8};
        System.out.println(solution(nums));
    }
}

 

그림으로 자세히 설명했으니 간단한 주석과 함께 곱씹어보면 감이 올 것이다.

여기까지 부분 배열의 합 중 가장 큰 값을 구하는 문제를 분할 정복을 통해 해결해보았다.