연속된 수중 가장 큰값을 리턴하는 부분수열

4가지 방법이 있지만 이중에서 분할 정복을 사용해서 문제를 풀것이다.

 

1. 왼쪽 경우에서 가장 큰값

2. 오른쪽 경우에서 가장 큰값

3. 겹치는 경우를 비교

 

 

 

 

public class sol {
    public static int solution(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return divideArr(nums, 0, nums.length-1);
    }

    public static int divideArr(int[] arr, int left, int right){
        if(left == right){// 배열의 길이가 1일 경우 전부 나눠진 경우 리턴
            return arr[left];
        }

        int mid = left + (right - left) / 2; // 절반씩 나누어서 진행
        int maxleft = divideArr(arr,left,mid);// 왼쪽에서 가장 작은 경우
        int maxRight = divideArr(arr,mid+1,right);// 오른쪽에서 가장경우
        int arrMax = findMax(arr,left,right,mid);// 겹치는 부분에서 가장 적은 경우

        return  Math.max(maxleft, Math.max(arrMax,maxRight));// 3개중에 가장 큰 경우를 출력해주면됨 
    }

    public static int findMax(int[] arr, int left, int right, int mid){
        int leftMax = Integer.MIN_VALUE;
        int sumLeft = 0;

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

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

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

        return rightMax + leftMax;
    }

    public static void main(String[] args){
        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));
    }
}