백준 1912 C++ - 연속합

Intro

문제 풀이 과정

문제해결을 위해 3가지 변수가 필요하다 생각했다.

1. 수열을 저장할 배열 arr[]
2. 최대합을 저장할 변수 maxSum
3. 현재 정보를 저장할 변수 cur

• 예제 입력 2를 예시로, 먼저 maxSum과 cur를 입력받은 순열의 첫번째 원소로 설정한다.
  • maxSum = 2
  • cur = 2
• 다음 원소인 1을 더한다. 최댓값이 갱신되어야한다.
  • maxSum = 3
  • cur = 3
• 다음 원소인 -4를 더한다.
  • cur = -1
• 다음 원소인 3을 더하려고 보니, 이전까지의 합인 cur에 3을 더해봤자 2밖에 안된다. 다음원소인 3보다 “작다”
  • cur는 2가아닌 3으로 갱신한다. 최댓값은 그대로다.
  • cur = 3
• 다음 원소인 4를 더한다. 최댓값이 갱신되어야한다.
  • maxSum = 7
  • cur = 7
• 다음 원소인 -4를 더한다.
  • maxSum = 7
  • cur = 3
• 다음 원소인 6을 더한다. 최댓값이 갱신되어야한다.
  • maxSum = 9
  • cur = 9
• 다음 원소인 5를 더한다. 최댓값이 갱신되어야한다.
  • maxSum = 14
  • cur = 14
• 다음 원소인 -5를 더한다.
  • cur = 9
• 다음 원소인 1를 더한다.
  • cur = 10
• 따라서 정답은 maxSum인 14가 된다.

소스코드

#include <iostream>
#include <algorithm>

using namespace std;

/*									<문제해결>
		규칙1. 연속된 몇 개의 수를 선택해서 구할 수 있는 최대합을 구해야한다.
		규칙2. 수는 한 개 이상 선택해야한다.
		
		문제해결을 위해 3가지 변수가 필요하다 생각했다.
		1.수열을 저장할 배열		arr[]
		2.최대합을 저장할 변수		maxSum
		3.현재 정보를 저장할 변수	cur		

		arr 배열에 수열을 저장한 뒤, 가장먼저 maxSum과 cur를 arr의 첫번째 원소로 설정한다.
		두번째부터는 arr를 순차적으로 검사하며 maxSu과 cur를 설정해주면된다.

		* 선택한 해결방법
		cur는 현재 arr의 원소와 현재 arr의 원소 + cur 중 더 큰것으로 업데이트 하면 된다.
		maxSum는 cur를 업데이트한 뒤, maxSum과 cur중 더 큰것으로 업데이트하면 된다.
	*/

int arr[100001];

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}

	int maxSum = arr[1];			
	int cur = arr[1];			

	for (int i = 2; i <= n;i++)
	{
		cur = max(cur + arr[i], arr[i]);

		if (cur > maxSum)
			maxSum = cur;
	}

	cout << maxSum;

	return 0;
}