Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

Question

I need an algorithm for real application.

Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. can anyone hint or give me a efficient algorithm or pesudocode for it?

Answer 1

Here is an $\mathcal{O}(n\log n)$ answer.

For example, let be A = [2, 4, 6, -9, 12, -20]. We assume zero-based indexing.

alg(A):
   cumulativeSums = [0]

   for x in A:
       y = the last element of cumulativeSums
       add y + x at the end of cumulativeSums

   sort cumulativeSums
   minDifference = infinity

   for i = 1, ... , length(cumulativeSums) - 1:
       dif = cumulativeSums[i] - cumulativeSums[i - 1]
       minDifference = min(minDifference, dif)

   return minDifference

Everything except for sorting is linear. In our example we compute

cumulativeSums = [0, 2, 6, 12, 3, 15, -5]

After sorting, we have

cumulativeSums = [-5, 0, 2, 3, 6, 12, 15]
minDifference = 3 - 2 = 1

Algorithm returns the absolute value of the optimal sum. One can easily modify it if he wants it to return a real sum and corresponding $i$ and $j$.