暴力和正解都写挂了啊啊啊啊啊啊啊啊考场写了2小时心态泵了啊啊啊啊啊

最大子段和III

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大，且满足这段和 $S(l,r)$ 的奇偶性和这段长度 $len(l,r)$ 的奇偶性恰好相同：

• $S(l,r) = len(l,r) \pmod 2$

输入格式

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 1 2 -4 3

样例输出 #1

5

提示

• 对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^3$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$-10^9 \leq a_i \leq 10^9$。

暴力：

#include <bits/stdc++.h>
using namespace std;
int n,qzh[200010],shu[200010],ans=-2147483647;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>shu[i];
    	qzh[i]=shu[i]+qzh[i-1];
	}
    for(int l=1;l<=n;l++){
    	for(int r=l;r<=n;r++){
    		if(((r-l+1)%2)==((qzh[r]-qzh[l-1])%2)){
    			ans=max(ans,qzh[r]-qzh[l-1]);
			}
		}
	}
	cout<<ans;
	return 0;
}

正解：

#include <bits/stdc++.h>
using namespace std;
int n,shu[200020],dp[200020],ans=-2147483647,length=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
       	cin>>shu[i];
       	if(i==1){
	   		dp[i]=shu[i];
	   		length++;
	   	}else{
	   		if(dp[i-1]+shu[i]>shu[i]){
	   			length++;
			}else{
				length=1;
			}
	   		dp[i]=max(shu[i],dp[i-1]+shu[i]);
		}
		//cout<<length<<' ';
		if(dp[i]>=ans && (length%2)==(dp[i]%2)){
			ans=dp[i];
		}
   	}
	cout<<ans;
	return 0;
}