查找子数组的最小绝对和 [英] Finding minimal absolute sum of a subarray

问题描述

有一个数组 A 包含（正负）整数。查找元素的绝对和最小的（连续）子数组，例如：

There's an array A containing (positive and negative) integers. Find a (contiguous) subarray whose elements' absolute sum is minimal, e.g.:

A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum

我从实现蛮力算法开始 O（N ^ 2）或 O（N ^ 3），尽管它产生正确的结果。但任务指定：

I've started by implementing a brute-force algorithm which was O(N^2) or O(N^3), though it produced correct results. But the task specifies:

complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

经过一些搜索我认为也许可以修改Kadane的算法来解决这个问题，但是我没有做到。

After some searching I thought that maybe Kadane's algorithm can be modified to fit this problem but I failed to do it.

我的问题是-Kadane的算法是否正确？如果没有，您能为我指明正确的方向吗（或在这里命名一个可以帮助我的算法）？我不需要现成的代码，只需要寻找正确算法的帮助即可。

My question is - is Kadane's algorithm the right way to go? If not, could you point me in the right direction (or name an algorithm that could help me here)? I don't want a ready-made code, I just need help in finding the right algorithm.

推荐答案

部分和
例如

If you compute the partial sums such as

2, 2 +(-4), 2 + (-4) + 6, 2 + (-4) + 6 + (-3)...

然后，任何连续子数组的和是两个部分和的差。因此，要找到绝对值最小的连续子数组，建议您对部分和进行排序，然后找到最接近的两个值，并使用原始序列中这两个部分和的位置来查找开始和结束

Then the sum of any contiguous subarray is the difference of two of the partial sums. So to find the contiguous subarray whose absolute value is minimal, I suggest that you sort the partial sums and then find the two values which are closest together, and use the positions of these two partial sums in the original sequence to find the start and end of the sub-array with smallest absolute value.

这里的昂贵位是排序，所以我认为它的运行时间 O（n * log（n））。

The expensive bit here is the sort, so I think this runs in time O(n * log(n)).

这篇关于查找子数组的最小绝对和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！