algorithm - 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. 计算累积和。
2. 解决。
3. 找到差异最小的顺序对。

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];
}

例子：

>>> 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]

在第一个示例中，[2, 3, 1]表示从索引2到3（含）的总和，您得到的绝对总和为1：

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