Boj 13398) 연속합 2

문제

백준 13398

설명

연속합 의 연장선 문제이다.

연속합은 누적합을 구하다가 0보다 작아지면 다시 처음부터 누적합을 구하는 방법으로 풀 수 있다. 여기서 값 하나를 뺏을 때의 최댓값은 점화식을 하나 세우면 해결할 수 있다. 이 두 경우를 비교해 최댓값을 출력해주면 된다.

\(v_i\) 번째 수까지 고려한 연속합을 \(A_{i}\), 여기서 딱 한 수만 제외할 때의 최댓값을 \(B_{i}\) 라고 하자. 그럼 \(B_{i+1} = \max(A_{i},\ B_{i} + v_{i+1})\) 로 점화식을 세울 수 있다. 이를 설명하자면, 새로 들어오는 \(v_{i+1}\) 을 무시한다면 이전의 누적합인 \(A_{i}\) 가 되고, 이전에 한번 무시한걸 유지한다면 \(B_{i}\) 에 \(v_{i+1}\) 를 더해야한다. 둘 중 작은 경우에서 수를 아무리 더해도 소용없으므로 최댓값만 고려하면 된다. 그래서 그리디 전략으로 둘 중 최댓값을 선택해 계속 업데이트를 하면 되는 것이다.

시간 복잡도

O(\(\mathrm{N}\))

코드

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

	int ans = -1e9, cur_acc = -1e9, left_one = 0;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		left_one = max(left_one + a, cur_acc);
		if (cur_acc < 0) cur_acc = a; 
		else cur_acc += a;
		ans = max(ans, max(cur_acc, left_one));
	}
	cout << ans;
}