Nearest [absolute value] sum of consecutive subsequence of a sequence of real values

Question

This is an algorithmic platform for me! I have seen variations of this problem considering the maximum sequential subsequence, but this is another variation. formal definition: A[1..n] find i and j so that abs(A[i]+A[i+1]+...+A[j]) closest to zero among others.

I am wondering how to get an O(n log^2 n) or even an O(n log n) solution.

Answer 1

• Calculate the total amount.
• Sorting.
• Find the consecutive pair with the smallest 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]; } 

<strong> 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 the sum from the index 2 to 3 (inclusive), and you get the absolute sum 1 :

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