查找最大交替的数字总和（python 3）-Java 学习之路

我被要求写一个函数，它找到给定数字和给定数字位数的最大交替数字和 . 例如，数字81010具有3个交替的和，长度为3 - （8-1 0），（1-0 1），（0-1 0），我们应该返回答案7 .

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

我想一想，如果给出前n位数的总和，我们就可以有效地找到从序列中的第二位开始的数字之和 .

请帮忙，谢谢 .

PS我确实看到了一些关于找到最大金额的问题，但无法实现找到最大交替金额的答案 .

这是找到连续数字的最大总和的代码：

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

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)

您询问了算法，因此应将其迁移到理论计算机科学站点 .

编辑：添加了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

回复于 2024-04-29T15:14:24+08:00

查找最大交替的数字总和（python 3）

1 回答

相关问题