분할 정복 문제 - 연속된 부분 배열의 합 중 가장 큰 값

// 정수형 배열 nums 가 주어졌다.
// 연속된 부분 배열의 합 중 가장 큰 값을 출력하세요.

// 입출력 예시
// nums: -5, 0, -3, 4, -1, 3, 1, -5, 8
// 출력: 10

// nums: 5, 4, 0, 7, 8
// 출력: 24

public class Main {

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

    private static int divideSubArray(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

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

        int maxLeft = divideSubArray(nums, left, mid); // left ~ mid 중 최대값 부분 배열 구하기
        int maxRight = divideSubArray(nums, mid + 1, right); // mid + 1 ~ right 중 최대값 부분 배열 구하기

        int maxArr = getMaxSubArray(nums, left, mid, right);  // left ~ mid 중 최대값 부분 배열 구하기

        return Math.max(maxLeft, Math.max(maxRight, maxArr));
    }

    /**
     * 부분 배열의 최대 구간 구하기
     */
    private static int getMaxSubArray(int[] nums, int left, int mid, int right) {
        int sumLeft = 0;
        int maxLeft = Integer.MIN_VALUE;

        //left와 right가 이어진 최대값 부분배열 구하기..
        for (int i = mid; i >= left; i--) {
            sumLeft += nums[i];
            maxLeft = Math.max(sumLeft, maxLeft); //max가 업데이트될 때 mid에서 left 방향의 서브어레이가 생긴다.
        }

        int sumRight = 0;
        int maxRight = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= right; i++) {
            sumRight += nums[i];
            maxRight = Math.max(sumRight, maxRight); //max가 업데이트될 때 mid + 1에서 right 방향의 서브어레이가 생긴다.
        }

//        return maxLeft + maxRight; // maxLeft + maxRight는 좌우 각각의 최대값을 갖는 부분 집합을 합치는 것.
        return Math.max(leftMax + rightMax, Math.max(leftMax, rightMax)); //leftMax + rightMax 더하기만 하는 게 맞나..? max 구하는게 맞지 않나..?
    }

    public static void main(String[] args) {
        // Test code
        int[] nums = {-5, 0, -3, 4, -1, 3, 1, -5, 8};
        System.out.println(solution(nums));

        nums = new int[]{5, 4, 0, 7, 8};
        System.out.println(solution(nums));
    }
}