题解 | 小苯的最大和

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int T;cin>>T;
    for(int i=0;i<T;i++)
    {
        int n;cin>>n;
        vector<long long> nums(n+1,0);
        for(int j=1;j<=n;j++)
        {
            cin>>nums[j];
        }

        //动态规划
        vector<long long> dp(n+1,0);
        if(n==1) {cout<<nums[1]<<endl;continue;}
        if(n==2) {cout<<(nums[1]+nums[2]>0?nums[1]+nums[2]:0)<<endl;continue;}

        dp[1] = nums[1];
        dp[2] = nums[2]+dp[1]>0?nums[1]+nums[2]:0;
        for(int j=3;j<=n;j++)
        {
            dp[j] = max({dp[j-2],dp[j-3],dp[j-1]+nums[j]});
            
        }

        // for(int j:dp)
        // {
        //     cout<<j<<" ";
        // }
        cout<<dp[n]<<endl;
    }
}
// 64 位输出请用 printf("%lld")