题解 | 小苯的最大和

def test(n:int,a:list):
    if n==1:
        return a[0]
    dp = [0 for _ in range(n+1)]
    dp[1]=a[0]
    for i in range(2,n+1):
        dp[i]=max(dp[i-1]+a[i-1],dp[i])
        dp[i]=max(dp[i],dp[i-2],dp[i-3])

    return dp[n]


if __name__ == "__main__":
    T = int(input())
    res = []
    for _ in range(T):
        n = int(input())
        a = list(map(int,input().split()))
        res.append(test(n,a))
    for i in res:
        print(i)