C++ 알고리즘 - 1921 연속합 (다이나믹 프로그래밍)

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

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

/******** 전역변수 ********/


/******** 함    수 ********/


int main(void) {
	/******** C++ INIT ********/
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	/******** 지역변수 ********/
	int input1;
	int input2;
	int sum = 0;

	vector<int> v;


	/******** 구    현 ********/
	cin >> input1;

	for (int i = 0; i < input1; i++) {
		cin >> input2;

		// 입력된 수가 양수면 합산
		if (input2 > 0) {
			sum += input2;
			continue;
		}

		// 음수면 합산된 수 - 음수를 벡터에 삽입
		//// 지금까지 합산한 수에 음수를 더해도 양수면 일단 계속 이어서 합산
		//// 더했는데 음수면 검증할 필요 없으니 패스
		else {
			if (sum != 0) v.push_back(sum);
			v.push_back(sum + input2);

			sum += input2;

			if (sum > 0) continue;
			else sum = 0;
		}
	}

	// 아직 수가 남아있으면 벡터에 삽입
	if (sum != 0) v.push_back(sum);

	// 벡터 정렬
	sort(v.begin(), v.end());

	// 가장 큰 값 출력
	cout << v[v.size() - 1];
}

 

순서대로 합산하되, 음수값을 발견하면 지금까지 합산한 것과 비교

두 수를 더했을때 음수라면 연속합에 포함시킬 필요가 없다.

음수를 더하기 이전의 값을 벡터에 저장하고 음수 다음의 값부터는 0으로 초기화, 다시 합산한다.

 

단, 예외 사항으로 음수만 입력될 수 있기 때문에 음수 발생 시의 값도 벡터에 저장해준다.

 

위 로직대로라면, 예제 1번대로 입력을 받은 경우

벡터의 값은 10, 6, 21, -14, 33, 32, 32가 순서대로 삽입된다.

이를 정렬하여 최대값인 33을 출력한다.