python - python中的最小子数组差异

Question

假设我有一个非空整数数组:A0..An .并考虑一个参数 P where 0 < P <=n .我需要找到被 P 分割的左右子数组之间的最小绝对差。例如:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

P = 1, difference = |3 − 10| = 7 
P = 2, difference = |4 − 9| = 5 
P = 3, difference = |6 − 7| = 1 
P = 4, difference = |10 − 3| = 7

这种情况下的解决方案是1

我完成了下面的代码:

def solution(A):
    lsum, rsum = A[0], sum(A[1:])
    diff = abs(rsum - lsum)
    p = 1
    while True:
        lsum += A[p]
        rsum -= A[p]
        next = abs(rsum - lsum)
        if next < diff:
            diff = next
            p += 1
        else:
            return diff

但我的解决方案有一些错误。它在某些情况下有效，但在某些情况下会返回错误的答案。例如:在类似 large sequence, numbers from -1 to 1, length = ~100,000 的情况下它返回错误的答案

P.S.:我完成了以下解决方案:

 def solution(lst):
    lsum, rsum = lst[0], sum(lst[1:])
    diff = abs(lsum - rsum)
    for i in xrange(1, len(lst) - 1):
        lsum += lst[i]
        rsum -= lst[i]
        ndiff = abs(lsum - rsum)
        diff = min(diff, ndiff)
    return diff

Answer 1

这更简洁但仍然是 O(n):

import itertools

def min_diff(A):
    total = sum(A)
    return min(abs(total - lsum - lsum) for lsum in itertools.accumulate(A))

itertools.accumulate从 Python 3.2 开始可用。