So I have a list of values like so
L1 = [-4 -3 5 8 ];
Note the sum of each element in L1 will always be > 0.
The operation I am performing on L1 is as follows
function applyRule: 1) Pick lowest value [ ex. -4 ] 2) Add it to its left and right neighbor [ left(-4) += -4; right(-4) += -4; ] 3) Invert sign picked in #1 [ invertSign(-4) ] 4) Repeat from step 1, until each element in L1 is non-negative 5) return the number of iterations taken end applyRule;`
A side note, the left and right neighbor of a element X at index i, is (i-1) and (i+1). In the case the rule is applied to the first element, its left neighbor is the last element, and in the case of the last element, its right neighbor is the first element. Like a circular list.
The problem I am having is counting the number of iteration the function applyRule will take efficiently for large list( ex. list of size > 10,000 with values ranging from -200,000 < x < 200,000 )
The idea I had was to create a function T, which would transform L1, and the proceed to apply the function applyRule, which returns the number of iteration take, which I could use to transform into the actual result. Hope the idea is clear. here is an example:
A = [-100 101 0]
Note: applyRule( A ) -> 200
The transform function maps A into this list
T(A)-> [-10 11 0] #note each element is divided by 10 and ceiled up
Then we apply the rule function:
applyRule( T(A) ) -> 20 #assume its true for now
Then we transform 20 into the actual result F(20) -> 200 #note we multiplied 20 by 10, since the function T divided by 10
Unfortunately, the above doesn't work for all cases. Can someone help me develop a transform function that works efficiently, for large list, or even list that meets certain requirements.