Dynamic Programming - Maximal Contiguous Subsequent Sum Problem

문제) N 개의 실수 A(1) ~ A(N)이 있을 때, 연속된 수 A(i) ... A(j)의 합이 최대가 되는 값을 구하라.

솔직히 Brute Force 방식으로 풀어도 O(N^3)의 복잡도를 가지므로,

NP-Complete 한 문제는 아니다.

하지만 D.P 연습으로 공부를 하는 거니깐.

내가 생각한 아이디어는 다음과 같다.

S[i][j] = A(i) ... A(j) 까지의 합이라고 할 때,

( j = i 인 경우) S[i][j] = A[j];

( j > i 인 경우 ) S[i][j] = S[i][j-1] + A[j];

요렇게 하면 따로이 Sum 루틴이 필요 없이,

착착 계산되어 진다는 거...

이 계산하면서 Max Sum 값을 체크하여 기억해 두면 OK.

간단하게 핵심 루틴만 적어본다면...

void find_max_sum() {
    int c, i, j;
    int max_s = 0, max_e = 0, max_sum = INT_MIN;


    for(c = 1; c <= NUM_OF_NUMBERS; c++) {   // subsequence count
        for(i = 0; i < NUM_OF_NUMBERS-c+1; i++) {   // start position
            j = i+c-1;
            if(c == 1) {
                S[i][j] = A[j];
            } else {
                S[i][j] = S[i][j-1] + A[j];
            }
            if(S[i][j] > max_sum) {
                max_sum = S[i][j];
                max_s = i;
                max_e = j;
            }
        }
    }
}

(2012.8.30 수정)

이 문제를 해결하는 좋은 알고리즘이 있었다.

Kadane's Algorithm 이다. (지나가던 과객님께 감사드립니다 (__) )

아이디어는 다음과 같은 것이다.

MaxSum(N) : N번째 원소가 포함된 Max Contiguous Subsequent Sum

MaxSum(N) : Max( MaxSum(N-1), A(N) )

( MaxSum은 굳이 배열이 아니라 그냥 변수 하나로 써도 된다 )

MaxSoFar : 계속 계산해 가던 MaxSum 들 중 최대값.

위키피디아의 파이썬 소스를 적어보면, 아래와 같다.

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

(C++ 코드)

int i = 0, j = 0, k = 0;
int MaxEnd, MaxSoFar;

MaxSoFar = MaxEnd = A[0];
for(int n = 1; n < NUM_OF_NUMBERS; n++) {
    MaxEnd = MAX(MaxEnd + A[n], A[n]);
    if(MaxEnd == A[n])
        k = n;
    if(MaxEnd > MaxSoFar) {
        MaxSoFar = MaxEnd;
        i = k;
        j = n;
    }
}

D.P 문제 중에는 난이도가 낮은 문제가 아닐까?