백준1912 - 연속합

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

1912번: 연속합

1차원 DP를 사용하였다. 변수를 최댓값과 진행상황 두가지로 만들어 풀었다. 진행상황과 그 다음 숫자가 더했을 때 0보다 작으면 진행상황을 0으로 갱신하는 규칙과 진행상황을 0으로 하는 과정에서 현재 최댓값이 음수이면 그 다음 숫자와 크기 비교를 하여 더 큰 값을 최댓값으로 갱신해준다. 진행 상황을 더한 경우 0이상이면 현재 진행상황을 갱신하고 최댓값도 진행상황과 현재 최댓값을 비교하여 더 큰 값으로 갱신한다.

 

ex1.) 1 2 4 -5 3 4 5

순서	최댓값	진행상황
1	1	1
2	1 + 2	1 + 2
3	1 + 2 + 4	1 + 2 + 4
4	1 + 2 + 4	1 + 2 + 4 - 5
5	1 + 2 + 4	1 + 2 + 4 - 5 + 3
6	1 + 2 + 4 - 5 + 3 + 4	1 + 2 + 4 - 5 + 3 + 4
7	1 + 2 + 4 - 5 + 3 + 4 + 5	1 + 2 + 4 - 5 + 3 + 4 + 5

 

ex2.) -2 -1 -3 -4 -5

순서	최댓값	진행상황
1	-2	-2
2	-1	0
3	-1	0
4	-1	0
5	-1	0

 

ex3.) 1 2 3 -7 3 4 5 -1

순서	최댓값	진행상황
1	1	1
2	1 + 2	1 + 2
3	1 + 2 + 3	1 + 2 + 3
4	1 + 2 + 3	0
5	1 + 2 + 3	3
6	3 + 4	3 + 4
7	3 + 4 + 5	3 + 4 + 5
8	3 + 4  +5	3 + 4 + 5 - 1

 

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

int main() {
	int n, num; //n은 숫자의 수, num은 원소
	int ans = 0, going = 0; //최댓값과 진행상황
	vector<int> v; //숫자 배열
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
	}

	//현재 최댓값과 진행상황을 첫번째 숫자로 갱신
	ans = v[0];
	going = v[0];

	for (int i = 1; i < v.size(); i++) {
		if (going + v[i] < 0) { //현재까지 진행한 상황에서 현재 숫자를 더했을 때 음수인 경우
			going = 0;
			if (ans < 0) { //현재까지 구한 값 중에서 최댓값이 음수인 경우
				ans = max(ans, v[i]); //최댓값과 현재 값 중 큰 값으로 대체
			}
		}
		else { //현재까지 진행한 상황에서 현재 숫자를 더했을 때 0이상인 경우
			going = going + v[i]; //진행 상황을 현재 숫자와 더해 갱신하고
			ans = max(ans, going); //최댓값을 이전 최댓값과 현재 최댓값으로 갱신
		}
	}

	cout << ans;
}