我试图抓住前缀总和概念背后的想法，看看由Codility here（蘑菇选择器问题）的前缀总和课程中提供的示例
我的理解是整个概念基于简单的属性，其中在数组A的两个位置A（pos_left，pos_right）之间找到所有元素的总和，使用第二个数组P，其中所有元素被连续求和并且搜索到的位置总和计算为 value（P（pos_right + 1）） - 值（P（pos_left））。
A 1 2 3 4 5 6
P 0 1 3 6 10 15 21
sum of all elements between A[2] and A[5] = 3+ 4 + 5 = 12
or using the prefix sums" P[5+1] - P[2] = 15 -3 = 12
问题 每个地方都有一条带有蘑菇的街道，由非空载体代表。鉴于采摘器的初始位置及其移动范围，可以寻找可能的最大蘑菇数量。
看一下这个例子，我不明白循环构造背后的逻辑。任何人都可以澄清这种算法的机制吗？ 其次，我发现这个例子中的positoin索引非常混乱和麻烦。通常的做法是将前缀加上的矢量“移位”在开始时为零吗？ （事实上，向量中的计数元素从python中的0开始，因为已经引起了一些混乱）。
解决方案
def prefix_sums(A):
n = len(A)
P = [0] * (n + 1)
for k in xrange(1, n + 1):
P[k] = P[k - 1] + A[k - 1]
return P
def count_total(P, x, y):
return P[y + 1] - P[x]
# A mushroom picker is at spot number k on the road and should perform m moves
def mushrooms(A, k, m):
n = len(A)
result = 0
pref = prefix_sums(A)
for p in xrange(min(m, k) + 1): # going left
left_pos = k - p
right_pos = min(n - 1, max(k, k + m - 2 * p))
result = max(result, count_total(pref, left_pos, right_pos))
for p in xrange(min(m + 1, n - k)):
right_pos = k + p
left_pos = max(0, min(k, k - (m - 2 * p)))
result = max(result, count_total(pref, left_pos, right_pos))
return result
我已经为一个小数组A= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]运行了一些例子，选择了位置k = 5和范围m = 3.我不明白创建范围以通过两个循环检查的逻辑。
我得到循环的以下参数
(p=, left_pos=, right_pos=)
loop 1 (0,5,8), (1,4,6),(2,3,5),(3,2,5)
loop 2 (0,2,5), (1,4,6), (2,5,7), (3,5,8)
rangies各不相同。为什么？
用于调试的版本
def mushrooms2(A, k, m):
n = len(A)
result = 0
pref = prefix_sums(A)
l1 =min(m, k) + 1
print 'loop p in xrange(min(m, k) + 1): %d' % l1
for p in xrange(min(m, k) + 1):
print 'p %d' % p
print 'A= %r' % A
print 'pref= %r' % pref
left_pos = k - p
right_pos = min(n - 1, max(k, k + m - 2 * p))
result = max(result, count_total(pref, left_pos, right_pos))
print 'left_pos = k - p= %d' % left_pos
print 'right_pos= min(n-1,max(k,k+m-2*p))= %d' % right_pos
print 'max'
print '(result %d' % result
print 'count_total(pref, left_pos, right_pos)) %r, %r, %r, %r' % (pref,left_pos, right_pos,count_total(pref, left_pos, right_pos))
print 'result= %d' % result
print 'next p'
l2=min(m + 1, n - k)
print 'loop xrange(min(m + 1, n - k)): %d' % l2
for p in xrange(min(m + 1, n - k)):
print 'p %d' % p
print 'A= %r' % A
print 'pref= %r' % pref
right_pos = k + p
left_pos = max(0, min(k, k - (m - 2 * p)))
result = max(result, count_total(pref, left_pos, right_pos))
print 'right_pos = k + p= %d' % right_pos
print 'left_pos = max(0, min(k, k - (m - 2 * p)))= %d' % left_pos
print 'max'
print '(result %d' % result
print 'count_total(pref, left_pos, right_pos)) %r, %r, %r, %r' % (pref,left_pos, right_pos,count_total(pref, left_pos, right_pos))
print 'result= %d' % result
print 'next p'
print 'result %d' % result
return result
你并不是唯一一个将循环结构视为反直觉的人，因为我不得不花费几分钟时间。这是我想出来的。
现在，您提供的链接中的解决方案进一步详细说明了最佳策略是以一种只改变方向一次的方式走在路径上。以这种方式，人们能够覆盖左右端点的范围，left_pos和right_pos似乎代表。
至于循环的细节，而不是根据循环变量（即p）来考虑循环，更容易找出循环过程中的变化，以及如何使用p。否则，弄清楚那些最小和最大表达式中的内容在开始时看起来有点太奇怪了。
例如，在第一个循环中，不要弄清楚该范围代表什么，试试left_pos如何受到p得到的不同值的影响。经过一番思考后，人们注意到left_pos以符合可能的左端点的方式发生变化。
具体来说，当p == 0，左端点是起始指数（即k），当p是min(m, k)时，则它是0（即k < m）或(k - m)。在前一种情况下，就左边的终点而言，它就会离开道路上有效的点范围。在后一种情况下，移动的数量禁止任何left_pos小于(k - m)的解决方案，因为从mazxswpoi到m移动中的那些指数是不可能的。
在第一个循环中对k的分配可以类似地解释。 min语句包括right_pos，这是可以达到的最右边的合法索引，它用于将正确的端点保持在允许的限制内。内部max语句具有(n-1)，因为它是k最不可能的值。 （即由于right_pos是起点）它也有一个表达式k。此表达式表示以下过程：
(k + m - 2 * p)动作向右移动。第二个循环只是第一个循环的反映，你可以通过调整我对第一个循环的解释来解释它。
至于你的第二个问题，我认为通常的做法是转移前缀和数组的索引。我通常在竞争性编程中使用这种方法进行在线竞赛，我在Python中使用的前缀和数组的实现如下所示。
(m - 2p)我对上面实现的直觉是：在def prefix_sums(A):
n = len(A)
P = [0] * n
P[0] = A[0]
for k in xrange(1, n):
P[k] = P[k - 1] + A[k]
return P
def count_total(P, x, y):
return (P[y] - P[x - 1] if x > 0 else P[y])
，我们有包容性总和P[x]。