[알고리즘]배열의 부분 최대합

[알고리즘]배열의 부분 최대합

주어진 배열에서 연속된 구간 중 합이 최대가 되는 곳을 찾는 문제이다.

다음과 같이 재열이 주어졌을 때, 2 ~ 4 구간의 합이 11로 최대값을 가진다. 이를 찾기 위한 첫 번째 방법은 배열을 순회하며 모든 구간의 합을 구하여 최대값을 찾는 것이다. 이를 코드로 표현하면 다음과 같다.

xxxxxxxxxx
int sol1(const vector<int>& arr)
{
    int max = INT_MIN;
    for (int i = 0; i < arr.size(); i++)
    {
        int sum = 0;
        for (int j = i; j < arr.size(); j++)
        {
            sum += arr[j];
            if (sum > max) max = sum;
        }
    }
​
    return max;
}

코드를 살펴보면 0부터 시작하여 모든 부분합을 확인하기 위해 for문을 이중으로 순회한다. 따라서 이 방법을 사용하면 O(n^2)의 시간 복잡도를 가지게 된다. 이 경우 배열의 크기가 매우 커진다면 값을 구하는 데 오랜 시간이 걸린다. 이것보다 빠르게 구하기 위한 방법으로 분할정복을 적용할 수 있다.

분할정복 알고리즘이란 주어진 문제를 작은 부분으로 분할하여 해결하여 답을 얻는 알고리즘이다. 이 문제에 분할정복 알고리즘을 적용하기 위해 부분합이 어떤 경우에 존재하는지 생각해보자.

xxxxxxxxxx
1. 배열을 절반으로 나누었을 때 왼쪽에 존재한다.
2. 배열을 절반으로 나누었을 때 오른쪽에 존재한다.
3. 배열의 중간에 걸쳐서 존재한다.

첫 째로 주어진 배열의 중앙부터 최대가 되는 부분합을 구한다. 그리고 배열을 절반으로 나누어 왼쪽 부분의 최대합과 오른쪽 부분의 최대합을 구한다. 그리고 이렇게 구한 세 값(중앙에 걸친 값, 왼쪽 값, 오른쪽 값) 중 최대가 되는 값을 가져오면 된다. 왼쪽의 값과 오른쪽의 값을 구하기 위해 배열을 나누고 이를 반복하면 결국 전체 배열의 부분 최대합을 구할 수 있다. 답을 구하기 위해 배열을 둘로 나누는 작업을 반복한다. 이 과정을 그림으로 나타내면 다음과 같다.

 

배열을 절반씩 나누는데는 logN만큼 소요된다. 따라서 분할정복을 통해 부분 최대합을 구하면 O(NlogN)의 시간 복잡도를 가진다. 이를 코드로 나타내면 다음과 같다.

xxxxxxxxxx
int sol2(const vector<int>& arr, int start, int end)
{
    if (start >= end) return arr[start];
​
    int mid = (start + end) / 2;
​
    //중앙에 걸친 부분합을 구한다.
    int sum = 0;
    int left = INT_MIN;
    for (int i = mid; i >= start; i--)
    {
        sum += arr[i];
        left = max(left, sum);
    }
    sum = 0;
    int right = INT_MIN;
    for (int i = mid + 1; i <= end; i++)
    {
        sum += arr[i];
        right = max(right, sum);
    }
​
    //재귀호출을 통해 왼쪽 부분배열과 오른쪽 부분배열의 최대 부분합을 구한다.
    int part = max(sol2(arr, start, mid), sol2(arr, mid + 1, end));
​
    return max(left + right, part);
}

먼저 배열의 중간에 걸친 최대합을 구한 뒤 재귀호출을 통해 왼쪽 부분과 오른쪽 부분을 나누어 부분 합을 구한다. 재귀 호출을 하면 해당 부분 배열에 대해 위 과정을 반복하고 최대값을 리턴한다. 만일 나누어진 부분의 크기가 1이라면 그 값만 리턴한다.

DP를 이용하면 이보다 더 빠르게 부분합을 구할 수 있는 방법이 있다. 한 번의 순회를 통해 최대값을 구하기 때문에 O(N)의 시간복잡도를 가진다. 배열을 순회하며 값을 하나씩 더하여 부분합을 구한다. 만일 부분합이 0보다 작다면 이전의 부분합은 무시하고 새로 추가된 값으로 갱신한다. 이렇게 구한 부분합들 중 최대가 되는 값을 찾는것이다. 이를 코드로 나타내면 다음과 같다.

xxxxxxxxxx
int sol3(const vector<int>& arr)
{
    int ret = 0;
    int psum = 0;
    for (int i = 0; i < arr.size(); i++)
    {
        psum = max(psum, 0) + arr[i];
        ret = max(psum, ret);
    }
    return ret;
}

 

위의 코드들을 10,000개 원소를 가진 배열로 측정한 결과는 다음과 같다.