题解 | 不相邻取数

n=int(input())
a=list(map(int,input().split()))
dp=[0]*n
for i in range(n):
    # 动态规划
    # 针对第i个元素arr[i]，要从dp[0]~dp[i-2] (因为不相邻，所以必须从i之前的两位开始)选择最大的一个值，
    # dp[i] = arr[i]+max{dp[0],dp[1]...dp[i-2]},
    # 由于arr[i]>0，所以没必要从0开始，dp[i]只与dp[i-2]和dp[i-3]有关
    dp[i]=a[i]+max(dp[i-2] if i-2>=0 else 0,dp[i-3] if i-3>=0 else 0)
print(max(dp))