题解 | #小苯的最大和#

• 定义: dp[i]为以下标i为结尾的最大子序列和

• 状态转移方程:

• 解释: 如果不删除,dp[i]可以由dp[i-1]转移过来; 如果删除,由裴蜀定理  ,一定可以从dp[i-3]及其之前的任意位置转移过来,我们使用一个变量在遍历过程中记录dp[i-3]的前缀最大值即可; 当然也可以从当前节点重新开始选数,即max()中取0的情况.

• 时间复杂度:O(n)

import sys
input = sys.stdin.readline
t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    a=list(map(int,input().strip().split()))
    if n == 1:#只有1个数,无法删除
            print(a[0])
            continue
    dp=[-float("inf")]*(n+1)
    dp[0] = 0 #为了让dp[3]正常计算,需要dp[0]=0,即不选前面的任何数
    dp[1]=a[0]
    dp[2]=a[0]+a[1]
	mx = -float("inf")
    for i in range(3,n+1):
        mx = max(mx, dp[i - 3])
        dp[i] = max(dp[i - 1], mx) + a[i - 1]
    print(max(max(dp[:-2]),dp[-1])) #不能以dp[-2]为结尾,因为不能只删除dp[-1]一个数