[BOJ/C++] 2559 수열

문제

https://www.acmicpc.net/problem/2559

풀이

투포인터 문제인줄 알았는데 투포인터로 연속 부분합 구할 때는 전부 양수여야 하므로 다른 방식을 이용해야 한다.

누적합 배열 이용!

코드

#include <iostream>

using namespace std;

int sum[100001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	int ans = -987654321;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		sum[i] = sum[i - 1] + tmp;
	}

	for (int i = k; i <= n; i++) {
		ans = max(ans, (sum[i] - sum[i - k]));
	}

	cout << ans;

	return 0;
}