题解 | 小苯的最大和

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=2e5+5;
vector<ll>a;
vector<ll>f;
 
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll T;
    cin>>T;
    while(T--){
        ll n;
        cin>>n;
        a.assign(n+1,0);
        f.assign(n+1,0);
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        f[1]=a[1];
        f[2]=max(f[0],f[1]+a[2]);
        for(ll i=3;i<=n;i++){
            ll t=max(f[i-3],f[i-2]);
            f[i]=max(t,f[i-1]+a[i]);
        }
        cout<<f[n]<<endl;
    }
}