[백준] 1912번 연속합

1912번: 연속합

#include <iostream> 
#include <vector> 
#include <queue> 
#include <tuple>
#include <algorithm>
using namespace std;

int main() {
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> inputNumbers(n);
	for (int i = 0; i < n; i++) {
		cin >> inputNumbers[i];
	}
	vector<int> sum(n);
	int maxSum = inputNumbers[0];
	sum[0] = inputNumbers[0];
	for (int i = 1; i < n; i++) {
		if (sum[i - 1] + inputNumbers[i] > inputNumbers[i])
			sum[i] = sum[i - 1] + inputNumbers[i];
		else 
			sum[i] = inputNumbers[i];
		if (sum[i] > maxSum) maxSum = sum[i];
	}
	cout << maxSum;
	return 0;
}

 

입력이 다음과 같이 들어왔을 때의 예를 살펴보자.

8
3 5 -3 2 2 -33 7 3 

앞에서부터 차례로 연속합을 구해서 i까지의 최대 연속 합을 sum[i]에 저장하고 최대 연속합이 나올 때마다 maxSum을 갱신하기로 하자.

양수를 더하면 항상 이득이기때문에 양수일 때에는 sum을 갱신한다.

sum[0] = 3, maxSum = 3

sum[1] = 8, maxSum = 8 이 된다.

하지만 그렇다고 음수인 -3을 더하면 sum[2]가 5로 줄어드니 새로 더해야 할까? 여기에서 멈춰야 할까?

계속 더하면

sum[2] = 5, maxSum = 8

sum[3] = 7, maxSum = 7

sum[4] = 9, maxSum = 9

이렇게 9를 얻을 수 있는데 새로 더하거나 멈추면 9를 놓치게 된다.

그럼 일단 음수가 나와도 계속 더하는 것으로 해보자.

sum[5] = -24, maxSum = 9

sum[6] = -17, maxSum = 9

sum[7] = -14, maxSum = 9

답은 maxSum인 9일까?

마지막에 7 3을 더하면 10이 나와서 정답은 10인데 9로 틀린 답을 내게 된다.

그럼 어떻게 했어야 할까?

-33까지 더하면 max[5] = -24, maxSum = 9이다.

그 다음 7이 나왔을 때 7부터 아예 새로 더하면 7이 될 것을 앞에서 구한 것을 굳이 연속해서 더해서 -17부터 시작할 필요는 없다. 부모가 빚을 물려준다면 아예 파산 신청을 하고 새로 시작하는 게 나은 것처럼 아예 7부터 새로 시작하도록 하자.

sum[6] = 7, maxSum = 9

sum[7] = 10, maxSum = 10

그러면 정답은 maxSum인 10이 된다.

 

그러면 언제 버리고 새로 시작해야 하는걸까?

앞에서 구한 연속 합에 나 자신을 더한 것보다 나 자신이 더 크다면 굳이 빚까지 상속받는 것보다는

나 자신부터 새로 시작하면 된다.