给定一个整数数组 a,每个元素表示一个位置上的数值。要求从数组中选择若干个元素,使得任意两个被选择的元素在原数组中都不相邻,并且所选元素的总和最大。函数 choose(a) 返回能够得到的最大总和,则横线处应填写
def choose(a):
if not a:
return 0
n = len(a)
if n == 1:
return a[0]
dp = [0] * n
dp[0] = a[0]
dp[1] = max(a[0], a[1])
for i in range(2, n):
dp[i] = __________________________
return dp[-1]
dp[i-1] + a[i]
max(dp[i-1], dp[i-2] + a[i])
max(dp[i-2], a[i])
dp[i-1] + dp[i-2]