python - 前缀和算法

Question

我试图通过 Codility here 的 Prefix Sum Lesson 中提供的示例来理解前缀和概念背后的思想。 (采蘑菇问题)

我的理解是，整个概念是基于简单的属性，其中为了找到数组 A 的两个位置 A(pos_left, pos_right) 之间所有元素的总和，使用第二个数组 P，其中所有元素连续求和，其中搜索总和计算为
值(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 

The problem
There is a street with mushroom at every place represented by a non-empty vector. Given the initial position of a picker and its movement range, possible maximum number of mushrooms to collect is looked for.

看着这个例子，我不明白循环构造背后的逻辑。任何人都可以澄清这个算法的机制吗？

其次，我发现这个例子中的 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)

范围不同。为什么？

调试版本

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

Answer 1

认为循环构造违反直觉的不止您一个，因为我也不得不花几分钟研究它。这是我的发现。

现在，您提供的链接中的解决方案进一步详细说明了最佳策略是以一种只改变方向一次的方式在路径上行走。以这种方式，可以覆盖具有左右端点的范围，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)因为不可能从k到 m 步中的那些索引。

分配给 right_pos在第一个循环中可以类似地解释。最小语句包括 (n-1) ，这是可以达到的最右边的合法索引，它用于将正确的端点保持在允许的范围内。内部 max 语句的特点是 k ，因为它是 right_pos 的最小可能值. (即由于 k 是起点)它还有一个表达式 (k + m - 2 * p) .此表达式表示以下过程:

• 向左走 p 步。
• 改变方向，向右走p步到达起点。
• 带着剩下的(m - 2p)向右走移动。

第二个循环只是第一个循环的反射(reflect)，您可以通过调整我对第一个循环的解释来简单地解释它。

关于您的第二个问题，我认为移动前缀和数组的索引不是常见的做法。我通常在在线编程竞赛中使用此方法，您在 Python 中使用的前缀和数组的实现如下。

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] ，我们有总和 A[0] + A[1] + ... + A[x] .