[백준][C++] 1912 연속합

1912 연속합

1912번: 연속합

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

연속된 수를 선택해 구할 수 있는 최댓값을 구하는 문제!

처음엔 좀 고민했지만, 곧 풀이를 생각할 수 있었다.

 

알고리즘

1. 1부터 N-1까지 반복문을 돌린다.
2. 만약 전 요소 + 현재 요소를 더한 값이 0보다 크다면, 현재 값에 전 값을 더해준다.
3. 그렇지 않다면 현재 요소를 0으로 바꾼다.

 

너무 간단하게 설명해서 나중에 이해가 안 될 나를 돕기 위해...

그림판으로 그려왔다. 로직이 순서대로 다 보여서 훨씬 이해가 잘 된다!

 

코드

#include<bits/stdc++.h>
using namespace std;
vector<int> vec;

int main()
{
	int len, answer = -1001;
	cin >> len;
	vec.resize(len);

	for (int i = 0; i < len; i++)
	{
		cin >> vec[i];

		answer = max(vec[i], answer);
	}

	if (answer > 0)
	{
		for (int i = 1; i < len; i++)
		{
			int previous = vec[i - 1];

			// 더했을 때 이득이라면
			if (previous + vec[i] > 0)
			{
				vec[i] += previous;
			}
			else
			{
				vec[i] = 0;
			}

			answer = max(answer, vec[i]);
		}
	}

	cout << answer;
}

오랜만에 고민 끝에 직접 푼 문제라 기분이 좋았다!!