最接近零[绝对值]实数值序列的连续子序列之和

Question

这对我来说是一个算法游乐场!我已经看到这个问题的变化处理最大连续子序列,但这也是另一个变化.正式的def:给定的A[1..n]发现i,j因此abs(A[i]+A[i+1]+...+A[j])最接近于零.

我想知道如何获得O(n log^2 n),甚至O(n log n)解决方案.

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