题解 | 小苯的最大和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll T;
    cin>>T;
    while(T--){
        ll n;
        cin>>n;
        vector<ll> nums(n),dp(n);
        for(ll i=0;i<n;i++)cin>>nums[i];
        if(n>=1) dp[0]=nums[0];
        if(n>=2) dp[1]=max(dp[0]+nums[1],(ll)0);
        if(n>=3)dp[2]=max(dp[1]+nums[2],max(dp[0],(ll)0));
        for(ll i=3;i<n;i++)dp[i]=max(dp[i-1]+nums[i],max(dp[i-2],dp[i-3]));
        cout<<dp.back()<<endl;
    }
    return 0;
}