you want to solve the problem for ( 1 , n ) where 1 is first array and n is the last array. for solving ( i, n) first solve ( i+1 , n ), thus you'll have a integer S, ( 0<= S <= a[i+1] ) and if S>= a[i] then s= s-a[i] , and if s<a[i] then s = a[i] — s. and you can easily use an array to save the sign of any numbers from 1 to n.

Let solve this task for all suffixes of array in increasing of size order. For last element it's easy, because it's in [0..a_n]. let f_i is the sum we get for a_i..a_n

Let's add 1 element. Then a_i — f_i + 1 is in [-a_i..a_i], so a_i — f_i + 1 or f_i + 1 — a_i is OK.