python - 查找最大交替数字和(python 3)

Question

我被要求编写一个函数，用于查找给定数字和给定位数的最大交替数字和。例如，数字 81010 有 3 个长度为 3 - (8-1+0),(1-0+1),(0-1+0) 的交替和，我们应该返回答案 7。

对每个数字子序列求和很容易，但这可能需要一段时间，而且算法应该足够快以处理非常大的数字。我不知道如何编写运行速度比普通函数更快的函数...

我有一条线索，它告诉我们如何通过给定前 n 个数字的总和，我们可以有效地找到序列中从第二个数字开始的数字的总和。

请帮忙，谢谢。

附言我确实看到了一些关于寻找最大和的问题，但无法实现寻找最大交替和的答案。

这是查找连续数字的最大和的代码:

def max_sum(n,d):
    number = list(map(int,str(n)))
    maximum = current = sum(number[:d])
    for i in range(0, len(number)-d):
        current = current - number[i] + number[i+d]
        if current > maximum: 
           maximum = current
    return maximum

Answer 1

1. Negate every even number (81010 -> 8 -1 0 -1 0), find biggest_sum_1 starting at an odd position
2. Negate every odd number (81010 -> -8 1 0 1 0), find biggest_sum_2 starting at an even position
3. Return max(biggest_sum_1, biggest_sum_2)

您要求提供算法，因此应将其迁移到 Theoretical Computer Science 站点。

编辑:添加了 python 代码

def max_alt_sum(n,d):
  number = list(map(int,str(n)))
  negatedEven = []
  negatedOdd = []
  for i,v in enumerate(number):
    if i%2==0:
      negatedOdd.append(v)
      negatedEven.append(-v)
    else:
      negatedOdd.append(-v)
      negatedEven.append(v)
  maximum = sum(negatedEven[:d])
  for i in range(0, len(str(n))-d+1):
    if i%2==0:
      current = sum(negatedOdd[i:i+d])
    else:
      current = sum(negatedEven[i:i+d])
    if current > maximum:
      maximum = current
  return maximum