我被要求编写一个函数,该函数查找给定数字和给定数字位数的最大交替数字总和。例如,数字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. 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
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句