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

출력

첫째 줄에 답을 출력한다.

풀이

다른 DP문제를 풀다가 연속합 개념이 나와서 이 문제 먼저 풀어보았다.

now_max는 현재 위치까지의 부분합 중 최대를 뜻한다.(부분합의 시작은 알 수 없다.) 따라서 input를 받을 때마다 now_max에 더해준다. input이 들어올 때마다 total_max와 비교하여 total_max를 갱신시킨다. 만약 now_max가 0보다 작다면, 다음 input을 굳이 now_max에 더하는 것보다 0에서부터 다시 시작하는 것이 값이 더 크므로 now_max를 0으로 초기화한다. 즉 다음 인덱스를 새로 구할 부분합의 처음으로 여기고 다시 시작한다.)

코드

#include <iostream>

using namespace std;

void continuous_sum(void);

int n, input, now_max;
int total_max = -1000;

int main(void)
{	
	continuous_sum();

	return (0);
}

void continuous_sum(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	int i = -1;
	while (++i < n)
	{
		cin >> input;
		now_max += input;
		if (now_max > total_max)
			total_max = now_max;
		if (now_max < 0)
			now_max = 0;
	}
	cout << total_max;

	return ;
}

맞았습니다~람쥐