Re-arranging an array of payments to ensure no negative running balance
Problem
The following problem was posited:
A company has a list of expected revenues and payments for the upcoming
year in chronological order. The problem is that at some moments in time
the sum of previous payments can be larger than the total previous revenue,
which would put the company in debt. To avoid this problem the company
takes a very simple approach: it reschedules some expenses to the end of
the year.
You are given an array of integers, where positive numbers represent
revenues and negative numbers represent expenses, all in chronological
order. In one move you can relocate any expense (negative number) to the
end of the array. What is the minimum number of such relocations to make
sure that the company never falls into debt (in other words: you need to
ensure that there is no consecutive sequence of elements starting from
the beginning of the array, that sums up to a negative number)?