[C++] 백준 1912번 - 연속합 (분할 정복 알고리즘)

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

접근

학교에서 마침 분할정복을 이용한 최대부분합을 배워서 이문제를 풀어봄 ㅎ

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <limits.h>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
using namespace std;
#define all(x) (x).begin(), (x).end() 

int maxSubArraySum(vector<int> &num, int l, int r) {

    if (l == r) //벡터에 원소가 하나만 있는 경우 
        return num[l];

    int m = (l + r) / 2; //벡터의 중간 지점에서 분할

    int leftMax = INT_MIN, sum = 0;
    for (int i = m; i >= l; i--) {
        sum += num[i];
        leftMax = max(leftMax, sum);
    }

    int rightMax = INT_MIN;
    sum = 0;
    for (int i = m + 1; i <= r; i++) {
        sum += num[i];
        rightMax = max(rightMax, sum);
    }

    //leftMax + rightMax는 인덱스l부터 r까지의 부분배열에서 구한 
    //최대 연속 부분합 중에서. 중간 부분 배열에 포함된 부분 배열에서
    //구한 최대 연속 부분합을 포함하는 경우 
    return max(max(maxSubArraySum(num, l, m), maxSubArraySum(num, m + 1, r)), leftMax + rightMax);


}

int main() {
    
    int n;
    scanf("%d", &n);
    vector <int> num(n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }

    int maxSum = maxSubArraySum(num, 0, n - 1);
    printf("%d", maxSum);
   
    
    return 0;
}

리뷰 

분할 정복 알고리즘을 사용했다

배열의 가운데를 나눈 후 왼쪽부분배열에서 최대연속 부분합을 구하고

오른쪽 부분 배열에서 최대 연속 부분합을 구한다 그리고 그 두개를 더하면 

중간 부분 배열에 포함된 부분 배열에서 구한 최대 연속 부분합을 포함하는 경우를 구할 수 있다

부분 최대합이 m을 걸쳐서 나올수도 있어서 이렇게 해준다

 

그리고 왼쪽부분배열에서 최대부분합과 오른쪽부분배열에서 최대부분합을 구하고 세개를 비교해서 가장 큰 값이 정답이다 

 

난 재귀함수가 너무 싫다... 왜냐면 어려워,,,

출처 

https://www.acmicpc.net/problem/1912