[1912번] 연속합

www.acmicpc.net/problem/1912

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

 

출력

첫째 줄에 답을 출력한다.

 

풀이

입력 받는 배열 arr을 처음부터 끝까지 하나씩 읽어나갈 때, 연속된 합을 저장하는 배열 drr에 값을 저장한다. 

i번째까지 읽어온 연속합이 i번째의 값보다 큰지, 작은지 비교하여 drr[i] 에는 그 둘 중 더 큰 값을 저장한다.

그리고 i번째 인덱스까지 연속해서 더해온 최대값과 i번째 인덱스의 값의 크기를 비교해서 더 큰 값을 max_sum에 저장한다. 

 

예를 들어, n = 10이고 배열의 입력이 10 -4 3 1 5 6 -35 12 21 -1 로 들어올 때,

n	값	최대 연속합
0	10	10
1	-4	6
2	3	9
3	1	10
4	5	15
5	6	21
6	-35	-14
7	12	12
8	21	33
9	-1	32

n=7일때, arr[7] = 12 > 12-14 이기 때문에 연속합은 12가 된다.

따라서 위 예시에서 가장 큰 연속합은 33이 된다.

 

코드

#include <iostream>
using namespace std;
 
int max(int a, int b) {
	if (a > b)
		return a;
	else
		return b;
}
 
int main() {
 
	int n;
	int arr[100001];
	int drr[100001];
	cin >> n;
 
	for (int i = 0; i < n; i++)
		cin >> arr[i];
 
	int max_sum = arr[0];
	drr[0] = arr[0];
 
	for (int i = 1; i <= n; i++) {
		drr[i] = max(arr[i], drr[i - 1] + arr[i]);
		if (max_sum < drr[i])
			max_sum = drr[i];
	}
 
	cout << max_sum;
 
 
	return 0;
}