최대 합 부분 배열 (Maximum sub-array problem)

최대 합 부분 배열을 찾는 세 가지 방법에 대해 알아보자, 먼저 최대 합 부분 배열이란, 배열의 부분 배열들 중 원소의 합이 최대가 되는 부분 배열을 의미한다. 아래 예시에서는 arr[2 .. 6]이 최대 합 부분 배열이다.

Largest Sum Contiguous Subarray - GeeksforGeeks

(1) 전체 탐색: O(n^2)

가장 기본적인 방법으로 부분 배열의 시작을 i, 배열의 끝을 j라고 하고 이중 반복문을 이용하여 전체 탐색한다.

int getMaxSumOfSubarrayWithBruteForce(const vector<int>& arr) {
    int maxSum = -1;
    int tmpSum = 0;
    for(int i = 0; i < arr.size(); i++) {
        tmpSum = 0;
        for(int j = i; j < arr.size(); j++) {
            tmpSum += arr[j];
            maxSum = max(maxSum, tmpSum);
        }
    }
    return maxSum;
}

(2) 동적 프로그래밍: O(n)

Kadane's Algorithm - (Dynamic Programming) - How and Why does it Work?

kadanes 알고리즘을 이용하면 O(n) 시간 복잡도로 문제를 해결할 수 있다. 가장 간단한 아이디어는 다음과 같다

• 마지막 원소가 i인 부분 배열의 최대 합을 sumArr[i]에 저장한다
• 만약 sumArr[i]가 0보다 크면 sumArr[i+1] = sumArr[i] + arr[i]를 저장한다
• 그렇지 않으면 sumArr[i+1] = arr[i]를 저장한다

실행 예시

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int getMaxSumOfSubarrayWithBruteForce(const vector<int>& arr) {
    int maxSum = -1;
    int tmpSum = 0;
    for(int i = 0; i < arr.size(); i++) {
        tmpSum = 0;
        for(int j = i; j < arr.size(); j++) {
            tmpSum += arr[j];
            maxSum = max(maxSum, tmpSum);
        }
    }
    return maxSum;
}

int getMaxSumOfSubarrayWithDP(const vector<int>& arr) {
    vector<int> sumArr; //sumArr[i] has maximum sum of arr[0..i]
    sumArr.resize(arr.size());

    sumArr[0] = arr[0];
    for(int i = 1; i < arr.size(); i++) {
        // sumArr[i-1] is less than 0, throw sumArr[i-1]
        // otherwise, add sumArr[i-1] to sumArr[i]
        sumArr[i] = max(sumArr[i-1], 0) + arr[i];
    }

    return *max_element(sumArr.begin(), sumArr.end());
}

int getMaxSumOfSubarrayWithDP2(const vector<int>& arr) {
    int maxSum = arr[0];
    int tmpSum = arr[0];

    for(int i = 1; i < arr.size(); i++) {
        tmpSum = max(tmpSum, 0) + arr[i];
        maxSum = max(tmpSum, maxSum);
    }

    return maxSum;
}

int main() {
    vector<int> arr{1, 0, 3, -40, 12, 3, 4, 5, -1, 12, 10};

    cout << getMaxSumOfSubarrayWithBruteForce(arr) << endl; // 45
    cout << getMaxSumOfSubarrayWithDP(arr) << endl; // 45
    cout << getMaxSumOfSubarrayWithDP2(arr) << endl; // 45
    return 0;
}