4

Give an Array of integers eg : 10, -10, -1, -1, 10 . I have to find minimum reallocations such that all the prefix sums of the array are >=0. The sum of all elements in the array
is assumed to be non-negative. In the above example, we can move -10 to the end of the array to make all prefix sum positive. Not sure how to approach this problem efficiently. Where taking a number and inserting it anywhere else is to be treated as one reallocation. The problem is to be solved for one more type of reallocation :

  1. Any negative number can be moved to the end of the array
rohit
  • 83
  • 7

1 Answers1

4

We can scan left to right, moving the minimum integer scanned so far to the end each time the sum of scanned integers goes negative. The proof idea is that, if we compare what this greedy algorithm does to any optimal solution OPT, whenever greedy and OPT have moved the same number of integers, greedy’s total moved is less than or equal (i.e., larger, since we’re moving negative numbers) than OPT’s, therefore greedy never does a move that puts it behind OPT.

import heapq


def min_relocations(lst):
    relocations = 0
    heap = []
    total = 0
    for x in lst:
        heapq.heappush(heap, x)
        total += x
        if total < 0:
            relocations += 1
            total -= heapq.heappop(heap)
    return relocations
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • @David I have updated the definition of reallocation; I missed putting it earlier. I think for the types of reallocation where one can move a negative number to the end of the array David's algorithm will work, not sure though – rohit Oct 28 '21 at 03:31