[백준]Baekjoon1912

문제링크 : https://www.acmicpc.net/problem/1912

연속한 숫자중에 최대치를 구하는 문제이다.

처음으로 문제를 풀 때는 수열을 돌면서 음수가 나오면 그 전까지의 합계를 저장하고

만약 합계가 0보다 작을 떄는 합계를 다시 초기화하여

그 다음부터 다시 합계를 시작하고 저장하는 식으로 문제를 풀었다.

#include <iostream>
#include <algorithm>
#include <cstring>

#define SIZE 1000001
using namespace std;

int arr[SIZE];
int main()
{
	memset(arr, -1, sizeof(int)*SIZE); //모든 수를 -1로 초기화
	long long n;
	scanf("%lld", &n); //받을 숫자의 갯수
	for (int i = 1; i <= n; i++) scanf("%d", &arr[i]); //주어지는 수열

	long long sum = arr[1], maximum = arr[1]; //arr[1]을 합계와 최대치로 설정

	for (int i = 2; i <= n; i++) {
		if (arr[i] < 0) { //만약 i번째 수가 음수일 경우 이 수를 더하면 합계가 작아지므로 
			maximum = max(sum, maximum); //그 전까지의 합계를 maximum과 비교하여 일단 저장
		}
		sum = sum + arr[i]; //합계
		if (sum < 0) { //합계가 음수가 나왔을 떄
			if (arr[i + 1] < 0) sum = arr[i]; //다음에 나올 수가 음수라면 sum을 arr[i]로 해줌
			else sum = 0; //아니라면 sum을 0으로 할당
		}
	}
	printf("%lld\n", max(sum, maximum)); //마지막 sum까지 반영하여 최종 최대치를 출력
}

최종적으로 문제는 맞췄지만 비효율적으로 코드를 짰음을 알고 좀더 간결하게

문제를 풀어보았다.

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
	long long n;
	long long num;
	int max = -1001; //나올 수 있는 가장 작은수가 -1000이므로 
					 //초기 최댓값은 -1001로 설정
	int sum = 0;
	scanf("%lld", &n);
	while (n--) {
		scanf("%lld", &num);
		sum += num; //숫자가 들어오면 일단 바로 더함

		if (sum > max) max = sum; //이 때 max보다 sum이 크다면 최댓값 조정
		if (sum < 0) sum = 0; //sum이 0보다 작다면 sum을 0으로 조정
	}
	printf("%d", max);
}