[스크랩] 최대 연속 부분 구간 합 문제를 푸는 알고리즘

아래의 예제는 '프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략' 이라는 책의 미리보기에서 확인할 수 있는 내용이다.

이를 통해 효율적인 알고리즘을 구성하면 수행시간이 얼마나 짧아 질 수 있는 가를 확인할 수 있다.

{ -7, 4, -3, 6, 3, -8, 3, 4 } 에서 최대의 합을 갖는 구간을 찾아서, 최대의 합을 출력하는 문제이다.

책의 예제를 Java 로 수정하면 아래와 같다.

알고리즘 구성에 따라 for 문을 한번만 사용하고서 답을 찾을 수도 있다.

이렇게 효율적인 알고리즘을 구성하는 것은 무엇보다 중요하다.

package algorithm;

public class EfficientMaxSum {

    static int[] array = { -7, 4, -3, 6, 3, -8, 3, 4 };

    // A[] 의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: $O(N^3)$
    public static int inefficientMaxSum(int[] A) {
        int N = A.length;
        int ret = Integer.MIN_VALUE;

        for (int i = 0; i < N; ++i)
            for (int j = i; j < N; ++j) {
                // 구간 A[i..j]의 합을 구한다.
                int sum = 0;
                for (int k = i; k <= j; ++k)
                    sum += A[k];

                ret = Math.max(ret, sum);
            }

        return ret;
    }

    public static int betterMaxSum(int[] A) {
        int N = A.length;
        int ret = Integer.MIN_VALUE;

        for (int i = 0; i < N; ++i) {
            int sum = 0;
            for (int j = i; j < N; ++j) {
                // 구간 A[i..j]의 합을 구한다.
                sum += A[j];
                ret = Math.max(ret, sum);
            }
        }
        return ret;
    }

    // 최대 연속 부분 구간 합 문제를 푸는 분할 정복 알고리즘
    // A[lo..hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(nlgn)
    public static int fastMaxSum(int[] A, int lo, int hi) {
        // 기저 사례: 구간의 길이가 1일 경우
        if (lo == hi)
            return A[lo];
        // 배열을 A[lo..mid], A[mid+1..hi]의 두 조각으로 나눈다.
        int mid = (lo + hi) / 2;
        // 두 부분에 모두 걸쳐 있는 최대 합 구간을 찾는다. 이 구간은
        // A[i..mid]와 A[mid+1..j] 형태를 갖는 구간의 합으로 이루어진다.
        // A[i..mid] 형태를 갖는 최대 구간을 찾는다.
        int left = Integer.MIN_VALUE;
        int right = Integer.MIN_VALUE;
        int sum = 0;

        for (int i = mid; i >= lo; --i) {
            sum += A[i];
            left = Math.max(left, sum);
        }
        // A[mid+1..j] 형태를 갖는 최대 구간을 찾는다.
        sum = 0;
        for (int j = mid + 1; j <= hi; ++j) {
            sum += A[j];
            right = Math.max(right, sum);
        }
        // 최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
        int single = Math.max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid + 1, hi));
        // 두 경우 중 최대치를 반환한다.
        return Math.max(left + right, single);
    }

    //  최대 연속 부분 구간 합 문제를 푸는 동적 계획법 알고리즘
    // A[] 의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(n)
    public static int fastestMaxSum(int[] A) {
        int N = A.length;
        int ret = Integer.MIN_VALUE;
        int psum = 0;

        for (int i = 0; i < N; ++i) {
            psum = Math.max(psum, 0) + A[i];
            ret = Math.max(psum, ret);
           
//            System.out.println("-------------------------");
            System.out.printf("%2d, %2d, %2d\n", A[i], psum, ret);
//            System.out.println("-------------------------");
        }
        return ret;
    }

    public static void main(String[] args) {

        System.out.println(fastestMaxSum(array));
    }
}

http://book.algospot.com/estimation.html