2

Suppose I have a variable number of integers, each of which can be of any value from negative to positive infinity, and not sorted in any particular order. For example:

-1, -1, -1, -2, 9

The "function" is evaluated by picking a starting point, and adding all the numbers up. For example, if I started with 3:

 3 - 1 =  2
 2 - 1 =  1
 1 - 1 =  0
 0 - 2 = -2 --> Negative
-2 + 9 =  7

There are periods where the sum is non-positive. However, if I started with 6:

6 - 1 =  5
5 - 1 =  4
4 - 1 =  3
3 - 2 =  1
1 + 9 = 10

Then at no point during the addition process is the sum non-positive.

Is there an formula or algorithm to efficiently determine the minimum starting value such that the partial sums are always positive?

Thank you for your time.

Parcly Taxel
  • 103,344
404 Name Not Found
  • 123
  • When you started with $3$, the most non-positive number you got was $-2$. So if you start with $3+3=6$, you won't get any number smaller than $3+-2=1$. This technique will always work. – Gerry Myerson Oct 12 '20 at 11:44

1 Answers1

1

The minimum starting value needed to make all partial sums positive is $1$ minus the minimum value reached when summing starting from $0$. As the numbers are arbitrary, the naive method is the most efficient one: sum starting from $0$, note the minimum value reached during the entire operation, negate and add $1$. The result is the optimal starting value.

Parcly Taxel
  • 103,344