题解|#C. Yarik and Array#

经典动态规划求最大子序和的问题，思路不算难，但是数据量比较大，这里应用一个小技巧

将dp的初始化大小始终设置为n+1的大小，这样能避免memset给许多不必要的下标内容赋值，可以减少时间复杂度

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
typedef long long ll;
ll a[M];
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n; cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		ll dp[n+1];
		memset(dp,0,sizeof(dp));
		dp[1]=a[1];
		ll ans=dp[1];
		for(int i=2;i<=n;i++){
			if(abs(a[i]%2)+abs(a[i-1]%2)==1){
				dp[i]=max(a[i],dp[i-1]+a[i]);
				ans=max(ans,dp[i]);
			}
			else
				{
					dp[i]=a[i];
					ans=max(ans,dp[i]);
				}
		}
		cout<<ans<<endl;
	}
	return 0;
}