Minimum removal of subarrays to make array equal to target-CodePudding

Lets say we have an array [5, 4, -2, 4, -3] and we want all elements to equal to 0. Subarrays can be used to add or subtract by 1. For example, I can add 1's from index 0 to 3, and then the list is [5 1, 4 1, -2 1, 4 1, -3 1]. That counts as one move. How to minimize the number of moves? My approach, although perhaps slow, was go through the list and if a number was positive, keep extending to the right until you reach a 0 or a negative. Then vice versa for negative. Then if that window was greater than 0, subtract all numbers in that range by the minimum so far. Else, if that window was less than 0, add all numbers in that range by abs(minimum) so far. For example:

[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]

That took 4 1 abs(-2) abs(-1) abs(-2) moves in total.

Is there a more efficient algorithm? Also, is my approach correct?

CodePudding user response：

The description of your algorithm seems to go in the right direction but it is incomplete so it's hard to determine if it is correct or not.

You can approach this by dividing the list in groups of consecutive positive, negative and zero values. For each group, you can bring all the numbers closer to zero for the whole subrange by the amount corresponding to the smallest absolute value. This will leave you with a new spread of groups on which you can repeat the process until all elements are zero.

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

Output:

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