BOJ #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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

 

---

소스코드(C언어)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define max(a,b) (a>b)?a:b
int N;
int num[100000];

int find_max(int start, int end);
int find_max_mid(int start, int mid, int end);

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

	int total = find_max(0, N - 1);
	printf("%d\n", total);
	return 0;
}

int find_max(int start, int end) {
	if (start == end)
		return num[start];
	else if (start < end) {
		int mid = (start + end) / 2;
		int c1 = find_max(start, mid);
		int c2 = find_max(mid + 1, end);
		int c3 = find_max_mid(start, mid, end);
		int m = max(c1, c2);
		m = max(m, c3);
		return m;
	}
	else return -1000000000;
}

int find_max_mid(int start, int mid, int end) {
	int tmp = 0, tmpM = -1000000000;
	for (int i = mid; i >= start; i--) {
		tmp += num[i];
		tmpM = max(tmpM, tmp);
	}
	tmp = tmpM;
	for (int i = mid + 1; i <= end; i++) {
		tmp += num[i];
		tmpM = max(tmpM, tmp);
	}

	return tmpM;
}

 

Idea

Divide and Conquer(분할 정복)으로 해결한다.

배열을 절반으로 나눈 후,

① 왼쪽 배열에서 연속합의 최대

② 오른쪽 배열에서 연속합의 최대

③ 가운데를 지나가는 연속합의 최대 중 최댓값을 고른다.