value(P(pos_right + 1))-value(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
问题
有一条街道,每个位置都有蘑菇,用非空向量表示。给出采摘者的初始位置和移动范围,寻找可能收集的最大蘑菇数量。
看了这个例子,我不理解循环结构的逻辑。有人能澄清算法的机制吗?
此外,我觉得这个例子中的位置索引非常令人困惑和繁琐。将向量与前缀和移位到开始的零点是常见做法吗?(在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