[Algorithm] 연속구간의 최대 합을 구하는 알고리즘

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

해당 포스트에서는 연속구간의 최대 합을 구하는 여러 알고리즘에 대해 포스팅하겠습니다.

 

 

 

문제 정의

정수로 이루어진 수열에 대해, 연속된 부분구간 중, 그 합이 최대가 되는 구간을 찾고자 합니다.

 

 

 

무차별 대입(brute force) 알고리즘

int bruteFroce(int[] arr) {
    int n = arr.length;
    int max = Integer.MIN_VALUE;

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum = 0;

            for (int k = i; k < j; k++) sum += arr[k];

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

$O(n^{3})$의 시간복잡도를 가집니다.

 

 

더 나은 무차별 대입 알고리즘

int betterBruteForce(int[] arr) {
    int n = arr.length;
    int max = Integer.MIN_VALUE;

    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            max = Math.max(max, sum);
        }
    }
    return max;
}

쓸데없는 부분합 부분을 제거하여 $O(n^{2})$의 시간복잡도를 가집니다.

 

 

분할정복(divide & conquer) 알고리즘

int divideConquer(int[] arr, int s, int e) {
    // base case
    if (s == e) return arr[s];

    int m = (s + e) / 2;
    int left = Integer.MIN_VALUE;
    int right = Integer.MIN_VALUE;
    int sum = 0;

    // 중간에 걸친 경우, 왼쪽 최대합을 구한다
    for (int i = m; i >= s; i--) {
        sum += arr[i];
        left = Math.max(left, sum);
    }

    // 중간에 걸친 경우, 오른쪽 최대합을 구한다
    sum = 0;
    for (int i = m + 1; i <= e; i++) {
        sum += arr[i];
        right = Math.max(right, sum);
    }

    // 걸치지 않고 양분된 구간 내에 속하는 경우
    int single = Math.max(divideConquer(arr, s, m), divideConquer(arr, m + 1, e));

    // 중간에 걸친 경우와 걸치지 않은 경우 중 높은 값을 반환한다.
    return Math.max(left + right, single);
}

이분법을 이용하여, 왼쪽구간과 오른쪽 구간으로 분할합니다.

그리고 최대합을 가지는 연속구간이 중간지점에 걸쳐있는경우와 그렇지 않은경우로 나눈 후, 둘 중 큰 값을 반환합니다.

구간이 중간지점에 걸쳐있는 경우, 무조건 해당 요소는 포함해야 하기 때문에 반복문도 중앙에서 양옆으로 퍼져나가는 식으로 반복합니다.

결국, $O(nlog_{n})$의 시간복잡도를 가집니다.

 

 

동적 프로그래밍(dynamic programming) 알고리즘

// 점화식 : dp[n] = max(0, dp[n-1]) + arr[n]
int dynamicProgramming(int[] arr) {
    int n = arr.length;
    int max = Integer.MIN_VALUE;
    int partialSum = 0;

    for(int i=0; i<n; i++) {
        partialSum = Math.max(0, partialSum) + arr[i];
        max = Math.max(partialSum, max);
    }

    return max;
}

arr[n]를 오른쪽 끝 요소로 갖는 최대 합 구간을 반환하는 dp(n)를 가정합니다.

dp(n)는 항상 최대 합 구간을 반환하므로, dp(n-1)도 항상 최대 합 구간을 반환하는 것은 자명합니다.

따라서, dp(n)는 dp(n-1)에서 arr[n]를 더한 값이 됩니다.

 

그런데 만약 특정 구간 i부터 j까지의 합이 음수라면(i <= j), 해당 구간은 포함하지 않아야 합니다. 즉, arr내에서 최대 합 구간은 무조건 j 다음에 존재한다는 뜻입니다. (dp함수는 n번째 요소를 끝 요소로 가지기 때문입니다.)

 

따라서, dp(n)이 항상 최대 합 구간을 반환하는것을 명확히 하기 위해, 점화식은 다음과 같이 설정합니다.

$$dp(n) = max(0, dp(n-1)) + arr[n]$$

 

위 점화식을 바탕으로, 0부터 n까지 인덱스를 돌면서 부분합을 구한 뒤, 음수가 되면 폐기하고 양수라면 부분합에 취합합니다. 이렇게 구한 부분합이 이전에 구한 최대값보다 크다면 최대값을 업데이트합니다.

 

위 알고리즘은 n번 반복하기 때문에 시간복잡도는 $O(n)$이 됩니다.

 

 

참고

구종만. 프로그래밍 대회에서 배우는 알고리즘 해결전략. 서울:인사이트, 2012.