closest to zero [absolute value] sum of consecutive subsequence of a sequence of real values

Question

this is an algorithmic playground for me! I've seen variations of this problem tackling maximum consecutive subsequence but this is another variation as well. the formal def: given A[1..n] find i and j so that abs(A[i]+A[i+1]+...+A[j]) is closest to zero among others.

I'm wondering how to get O(n log^2 n), or even O(n log n) solution.

Answer 1

1. Calculate the cumulative sum.
2. Sort it.
3. Find the sequential pair with least difference.

function leastSubsequenceSum(values) {
    var n = values.length;

    // Store the cumulative sum along with the index.
    var sums = [];
    sums[0] = { index: 0, sum: 0 };
    for (var i = 1; i <= n; i++) {
        sums[i] = {
            index: i,
            sum: sums[i-1].sum + values[i-1]
        };
    }

    // Sort by cumulative sum
    sums.sort(function (a, b) {
        return a.sum == b.sum ? b.index - a.index : a.sum - b.sum;
    });

    // Find the sequential pair with the least difference.
    var bestI = -1;
    var bestDiff = null;
    for (var i = 1; i <= n; i++) {
        var diff = Math.abs(sums[i-1].sum - sums[i].sum);
        if (bestDiff === null || diff < bestDiff) {
            bestDiff = diff;
            bestI = i;
        }
    }

    // Just to make sure start < stop
    var start = sums[bestI-1].index;
    var stop = sums[bestI].index;
    if (start > stop) {
        var tmp = start;
        start = stop;
        stop = tmp;
    }

    return [start, stop-1, bestDiff];
}

Examples:

>>> leastSubsequenceSum([10, -5, 3, -4, 11, -4, 12, 20]);
[2, 3, 1]

>>> leastSubsequenceSum([5, 6, -1, -9, -2, 16, 19, 1, -4, 9]);
[0, 4, 1]

>>> leastSubsequenceSum([3, 16, 8, -10, -1, -8, -3, 10, -2, -4]);
[6, 9, 1]

In the first example, [2, 3, 1] means, sum from index 2 to 3 (inclusive), and you get an absolute sum of 1:

[10, -5, 3, -4, 11, -4, 12, 20]
         ^^^^^