寻找子阵列的最小绝对和

Question

有一个A包含(正和负)整数的数组.找到一个(连续的)子数组,其元素的绝对和是最小的,例如:

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

我已经通过实施蛮力算法,这是开始O(N^2)还是O(N^3),虽然它产生正确的结果.但任务规定:

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

经过一番搜索,我认为也许可以修改Kadane的算法以适应这个问题,但我没有做到.

我的问题是 - 卡丹的算法是正确的方法吗？如果没有,你能指出我正确的方向(或命名一个可以帮助我的算法)？我不想要现成的代码,我只需要帮助找到合适的算法.

Answer 1

如果计算部分总和 如

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

那么任何连续子阵列的总和就是两个部分和的差值.因此,为了找到绝对值最小的连续子阵列,我建议您对部分和进行排序,然后找到最接近的两个值,并使用原始序列中这两个部分和的位置来查找开始和结束绝对值最小的子阵列.

这里的昂贵的一点是那种,所以我认为这是及时的O(n * log(n)).

Answer 2

这是Saksow算法的C++实现.

int solution(vector<int> &A) {
    vector<int> P;
    int min = 20000 ;
    int dif = 0 ;
    P.resize(A.size()+1);
    P[0] = 0;
    for(int i = 1 ; i < P.size(); i ++)
    {
        P[i] = P[i-1]+A[i-1];

    }
    sort(P.begin(),P.end());
    for(int i = 1 ; i < P.size(); i++)
    {
         dif = P[i]-P[i-1];
         if(dif<min)
         {
             min = dif;
         }
    }
    return min;
}

Answer 3

我正在对Codility进行这项测试,我发现mcdowella的答案非常有帮助,但还不够,我不得不说:所以这里是2015年的答案!

我们需要构建数组A的前缀和(这里称为P),如:P [0] = 0,P [1] = P [0] + A [0],P [2] = P [1] + A [1],...,P [N] = P [N-1] + A [N-1]

A的"min abs sum"将是P中2个元素之间的最小绝对差值.所以我们只需要.sort()P并循环遍历每次2个连续元素.这样我们得到O(N + N log(N)+ N)等于O(N log(N)).

而已!