[Algorithm] 연속 구간의 최대 합 구하기

규정 상의 이유로 출처와 문제는 밝힐 수 없지만 코딩테스트를 보다가 연속 구간의 최대 합을 구하는 문제를 접하게 되었습니다.

문제를 푸는 방법이 굉장히 다양하고 각 풀이 방법의 복잡도가 전부 다르기 때문에 이에 대해서 정리해보고자 합니다.

 

연속 구간의 합

우선 main 함수입니다.

main 함수에서는 원소의 개수를 입력받고, 원소의 개수만큼 값들을 입력받아 배열에 저장합니다.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
	int N;
    vector<int> arr;

	cin >> N;
	
	for (int i=0;i<N;i++){
        int temp;
        cin >> temp;
		arr.push_back(temp);
	}
	
    int result = brute_force(arr);
    cout << result << "\n";
	return 0;
}

 

Brute Force

첫 번째 방법은 Brute Force 입니다.

모든 구간의 합을 전부 계산하여 비교하는 방식이죠.

시간복잡도는 O(n^3) 입니다.

int brute_force(vector<int> arr){
    int size = arr.size();
    int result = INT_MIN;

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

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

            result = max(result, sum);
        }
    }
    return result;
}

 

Brute Force 2

마찬가지로 Brute Force 이지만 불필요한 연산을 많이 개선하였습니다.

예를 들어 위의 경우, 3번째 원소부터 7번째 원소까지의 합과 3~8까지의 합을 각각 다시 계산하게 되지만 개선된 방법에서는 3~7까지 구한 값에서 8번째 값을 더해줌으로서 복잡도를 낮추었습니다.

시간복잡도는 O(n^2) 입니다.

int brute_force2(vector<int> arr){
    int size = arr.size();
    int result = INT_MIN;

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

 

Divide And Conquer

이번에 사용할 방법은 Divide And Conquer 입니다.

전체의 부분합을 구하기 위해서 절반씩 나눠 작은 문제로 쪼갠 후 계산을 하게 됩니다.

하지만 여기서 문제점은 부분합의 최대값이 작은 문제에 걸쳐있는 상황입니다.

예를 들어 {-3, 0, -1, 3, 5, -2, -4} 의 부분합의 최대값은 3+5로 8이지만 절반으로 나눠 각각 계산하면 이를 구할 수 없습니다.

따라서 작은 문제로 나누기 전, 걸치는 상황에 대해 계산을 우선적으로 해줍니다.

시간복잡도는 O(nlogn) 입니다.

int divide_and_conquer(vector<int> arr, int start, int end){
    if (start == end) return arr[start];

    int result = INT_MIN;
    int mid = (start + end) / 2;

    // 부분합의 최대값이 mid를 포함하여 걸치는 상황
    int left = INT_MIN;
    int right = INT_MIN;

    int left_sum = 0;
    int right_sum = 0;

    for (int i=mid;i>=start;i--){
        left_sum += arr[i];
        left = max(left, left_sum);
    }

    for (int i=mid+1;i<=end;i++){
        right_sum += arr[i];
        right = max(right, right_sum);
    }

    // 부분합이 mid를 기준으로 한 쪽에 생기는 상황
    result = max(divide_and_conquer(arr, start, mid), divide_and_conquer(arr, mid+1, end));
    result = max(result, left+right);
    return result;
}

 

Dynamic Programming

마지막으로 Dynamic Programming 입니다.

dp 점화식을 정의해봅시다.

dp[i]를 arr[i]를 오른쪽 끝으로 하는 구간의 최대 합으로 정의해봅시다.

이 때 dp[i+1]와 dp[i] 의 관계를 생각해보면 arr[i+1]가 추가되었을 때 arr[i+1] 를 그 전까지의 최대 dp[i]와 더한 값 혹은 독자적으로 arr[i+1] 값 중 하나가 dp[i+1] 이 됩니다.

그 후 dp[i] 를 전부 순회하면서 최대값을 찾으면 됩니다.

복잡도는 O(n) 입니다.

int dynamic_programming(vector<int> arr){
    int result = INT_MIN;
    int size = arr.size();
    vector<int> dp(size);

    for (int i=0;i<size;i++){
        if (dp[i-1] + arr[i] > arr[i]) dp[i] = dp[i-1] + arr[i];
        else dp[i] = arr[i];
    }

    for (int i=0;i<size;i++){
        result = max(result, dp[i]);
    }

    return result;
}