연속합 구하기

Sum_in_a_row.cc

#include<iostream>

using namespace std;

int main()
{
	int N;//정수 갯수
	int arr;
	int now_sum, max_sum;
	int max_num;//입력 받은 수 중 최대 수

	cin >> N;

	//변수 초기화
	cin >> arr;
	max_num = arr;
	max_sum = arr;
	now_sum = arr;

	for (int i = 1; i < N; i++)
	{
		cin >> arr;

		//입력받은 수 중 가장 큰 수 구함
		if (max_num < arr)
			max_num = arr;

		now_sum += arr;
		if (now_sum < 0) //만약 현재까지 더한 수가 음수라면
			now_sum = 0; //다시 연속 합을 찾는다.
		if (max_sum < now_sum)//최대합보다 이때까지의 연속합이 더 크다면
			max_sum = now_sum;//최대합 갱신
	}

	if (max_sum <= 0) //만약 모든 수가 음수였다면
		max_sum = max_num; //입력 받은 수 중 최대 수가 정답

	//출력
	cout << max_sum << endl;

	return 0;
}