CS Academy Max Even Subarray

リンク : https://csacademy.com/contest/archive/task/max-even-subarray/

問題概要

長さNの数列が与えられる。数列から連続した偶数個を取り出したときの最大値を求めよ。

解説

前から偶数個取り出した結果が負であれば、その次の2個を取り出すときは無視してよい。例 (2,-16,6,7) から[0,1]を取り出したとき 2-16<0 である。次の[2,3]を取り出すときは、[0,1]が負なら[0,3]は[2,3]より必ず小さくなる。

このことを使うと前から順番に線形時間で求めることができる。

実装でfor文で書こうとしたら条件を考えるのがめんどくさかったからwhileで書いた

    LL n,ans, sum[110000],a[110000];
int main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, n) {
		sum[i + 1] += sum[i] + a[i];
	}
	LL num = 0,i=0;
	ans = -INF;
	while(i*2+1<n){
		num += a[i * 2] + a[i * 2 + 1];
		ans = max(ans, num);
		if (num < 0)num = 0;
		i++;
	}
	num = 0, i = 0;
	while (i * 2 + 2 < n) {
		num += a[i * 2 + 1] + a[i * 2 + 2];
		ans = max(ans, num);
		if (num < 0)num = 0;
		i++;
	}
	cout << ans << endl;
	return 0;
}