[Algorithm] 연속 구간 최대 합 구하기

😁 연속 구간의 최대 합 구하기

다양한 방법의 풀이 방법이 존재하는 주어진 배열에서 연속 구간의 최대 합 구하기 알고리즘을 Java 언어와 분할 정복으로구현하였으며 시간 복잡도는 O(nlgn) 이다.

예제로 풀이한 아래 코드에서 최대합은 14 로 결과가 나온다.

public class MaxNumber {

    private static Integer [] numArrs = {-7,-1-2,0,10,4,-1};
    private static List<Integer> numbers = Arrays.asList(numArrs);
    private static Integer MIN = Collections.min(numbers);

    public static void main(String[] args) {

        System.out.println(maxSum(numArrs, 0,numArrs.length-1));

    }

    public static int maxSum(Integer [] numArrs,int start, int end){
        /**
         * 기저사례 구간의 길이가 1
         */
        if(start == end) return numArrs[start];

        int mid = (start + end) /2;
        /**
         *  두 부분에 걸쳐있는 최대의 합 구간을 찾기
         */
        int left = MIN, right = MIN, sum =0;

        for(int i= mid; i>=start; i--){
            sum += numArrs[i];
            left = Math.max(left, sum);
        }

        sum =0;

        for(int j=mid+1; j<=end;j++){
            sum += numArrs[j];
            right = Math.max(right, sum);
        }
        /**
         *  최대값이 한쪽에 생기는 부분 재귀호출
         */
        int single = Math.max(maxSum(numArrs, start, mid), maxSum(numArrs, mid + 1, end));

        // 두경우중 최대치를 반환
        return Math.max(left + right, single);

    }

}