문제

문제 링크

해설

• 수열의 길이는 최대 10만이므로 연속해서 합산할 범위의 시작점과 끝점을 두 개의 for문을 사용해서 모든 경우의 수를 구하는 O(n²) 알고리즘이 가장 간단하지만, 시간 내애 풀 수 없습니다.
• N개의 수열을 입력받으면서 특정 조건을 적용해 최적해를 빠르게 구하는 라인스위핑 알고리즘을 적용해야 합니다.
• 지금까지 더한 수를 sum, 다음 번 수를 number라고 합시다.
  • number > 0 인 경우, 무조건 더하는 게 이득입니다.
  • number < 0 인 경우는 한 단계 더 생각해야 합니다.
    • sum + number > 0 이라면, 일단은 더하는게 이득입니다. 왜냐하면, 새로운 sum을 하나의 양수로 취급할 수 있기 때문입니다.
      • <예제입력 1>의 10 - 4 3 1 ... 에서, 10과 -4를 더한 것을 6으로 취급하면, -4를 만났다고 10을 버리고 3부터 새로 시작하는 것보다 계속 더하는 것이 이득인 것을 알 수 있습니다.
    • sum + number < 0 이라면, 새로 시작하는 것이 낫습니다.
      • <예제입력 1>에서 앞 7개 원소를 더하면 -14입니다.
      • 이 값을 버리고 12부터 새롭게 시작하는 것이 이득인 것을 알 수 있습니다.
• 위 과정을 코드로 그대로 옮기면 O(n)으로 최적해를 구할 수 있습니다.
• 이때, 초깃값 설정을 주의합시다. 수열 내 수의 범위가 -1,000 ~ 1,000 이기 때문에 정답을 저장한 변수의 초깃값은 저 범위 바깥에 있는 것이 안전합니다.

코드

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N;
	cin >> N;

	int answer = -1'001, sum = 0;
	for (int i = 0; i < N; ++i) {
		int n;
		cin >> n;
		sum += n;
		answer = max(answer, sum);
		if (sum < 0) sum = 0;	// 누적합이 음수면 버리고 새로시작.
	}
	cout << answer;
}

소스코드 링크

결과