最大和 跳过两个连续整数

Question

我需要返回跳过两个连续值的数组N的最大和。 例如， N=[10，30，50，60，5，60]。 输出：175，跳过前两个值[10,30]=40

我写了这个：

def maxSum(array):
  tempSum = sum(array)
  totalSum=0
  for i in range(len(array)):
    prevSum = tempSum - sum(array[i:i+2])
    if prevSum > totalSum:
      totalSum = prevSum

有没有什么方法可以通过贪婪、DAC或动态程序来解决这个问题

Answer 1

这种方法是O(n)和贪婪的：

N = [10, 30, 50, 60, 5, 60]

total = sum(N)
result = max(total - sum(pair) for pair in  zip(N, N[1:]))

print(result)

输出

175