最小删除子数组以使数组等于目标

Question

假设我们有一个数组 [5, 4, -2, 4, -3] 并且我们希望所有元素都等于 0。子数组可用于加或减 1。例如，我可以从索引 0 到 3 添加 1，然后列表为 [5 + 1, 4 + 1, -2 + 1, 4 + 1, -3 + 1]。这算作一步。如何最小化移动次数？我的方法虽然可能很慢，但是遍历列表，如果数字是正数，则继续向右延伸，直到达到 0 或负数。然后反之亦然。然后，如果 window 大于 0，则将该范围内的所有数字减去到目前为止的最小值。否则，如果 window 小于 0，则将到目前为止该范围内的所有数字相加 abs(minimum)。例如：

[5, 4, -2, -5, -3]
5 is start, 4 is end since we reach end of positives. Minimum so far is 4. 
[5 - 4, 4 - 4, -2, -5, -3] = [1, 0, -2, -5, -3]

[1, 0, -2, 4, -3] 1 is start, 1 is end. minimum so far is 1.
[1 - 1, 0, -2, -5, -3] = [0, 0, -2, -5, -3]

We go to 0, but we skip it 
[0, 0, -2, -5, -3]  -2 is start, -3 is end. abs(-2) is minimum so far
[0, 0, 0, -3, -1] -3 is start, -1 is end. abs(-1) is minimum so far
[0, 0, 0, -3 + 1, -1 + 1] = [0, 0, 0, -2, 0]

[0, 0, 0, -2, 0] -2 is start, -2 is end. abs(-2) is minimum so far
[0, 0, 0, -2 + 2, 0] = [0, 0, 0, 0, 0]

总共走了 4 + 1 + abs(-2) + abs(-1) + abs(-2) 步。

有没有更高效的算法？还有，我的做法对吗？

Answer 1

您对算法的描述似乎朝着正确的方向发展，但它不完整，因此很难确定它是否正确。

您可以通过将列表分成连续的正值、负值和零值组来解决这个问题。对于每个组，您可以通过对应于最小绝对值的量使整个子范围内的所有数字更接近零。这将为您留下新的组分布，您可以在这些组上重复该过程，直到所有元素都为零。

from itertools import groupby

def incdec(A):
    count  = 0
    while any(A):
        groups = (list(g) for _,g in groupby(A,lambda n:(n>0)-(n<0)))
        A = []
        for group in groups:
            moves = min(group,key=abs)
            count += abs(moves)
            A.extend(n-moves for n in group)
    return count

输出：

print(incdec([5, 4, -2, -5, -3]))  # 10
print(incdec([5, 4, -2, 4, -3]))   # 14             
print(incdec([5, 3, 4, 2, 3, 0, 1, 1 , -2, -4, -3])) # 12

# sample process expansion:
#
# [5, 3, 4, 2, 3, 0, 1, 1 , -2, -4, -3]
# [5, 3, 4, 2, 3], [0], [1, 1],[-2, -4, -3]
#  -2                    -1     +2                5 moves
# [3, 1, 2, 0, 1, 0, 0, 0 , 0, -2, -1]
# [3, 1, 2], [0], [1], [0, 0, 0 , 0], [-2, -1]
#  -1             -1                   +1         3 moves
# [2, 0, 1, 0, 0, 0, 0, 0 , 0, -1, 0]
# [2], [0], [1], [0, 0, 0, 0, 0 , 0], [-1], [0]
# -2        -1                         +1         4 moves
#                                                ---------
#                                                12 moves

最小删除子数组以使数组等于目标

Minimum removal of subarrays to make array equal to target

python

arrays

algorithm

search

sub-array