寻找子数组的最小绝对和

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 算法可以被修改以适应这个问题，但我没有成功。

我的问题是 - Kadane 算法是否是正确的选择？如果不是，你能指导我正确的方向（或者提供一个可以帮助我的算法的名称）吗？我不需要现成的代码，只是需要找到正确的算法。

- NPS

Answer 1

如果您计算偏和 ，则如下所示：

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

那么任何连续子数组的和都是两个部分和之间的差。因此，为了找到绝对值最小的连续子数组，我建议您对部分和进行排序，然后找到两个最接近的值，并使用这两个部分和在原序列中的位置来找到具有最小绝对值的子数组的开头和结尾。

这里比较昂贵的是排序，因此我认为时间复杂度为 O(n * log(n))。

- mcdowella

---

我不明白你是如何从部分和中确定子数组的。例如，数组[-4,5,-1]的部分和为[-4,1,0]，你似乎暗示这意味着子数组应该是[5，-1]=4，但实际上解决方案是[-4,5，-1]=0。 - Benubird

我没有考虑整个数组，而是将其视为子数组。你可以单独考虑具有小部分和的子数组，或者在对所有内容进行排序时确保包括具有零元素的子数组 - 这样它的总和就为零，在你的例子中，你会得到部分和[-4,1,0,0]，并找出从两个零和所加的术语之间的跨度考虑得出的解决方案 - 整个数组的开始和结束。从两个部分和中确定的子数组是在其中大多数项目被求和但不在另一个项目中的部分和集合。 - mcdowella

考虑3,3,3,4,5？也许我很困惑。 - Catalyst

部分和为0、3、6、9、13、18（包括前0个元素的部分和），已经排序，其中3和6是最接近的一对数字，因此具有最小绝对部分和的连续子数组的一个答案是[3]。据我所知，这是正确的答案，除非您允许零长度的部分和，如果允许，则每个输入的正确答案都将是零长度的部分和。 - mcdowella

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

- Louie Lu

Answer 3

我在Codility上做了这个测试，发现mcdowella的答案非常有帮助，但还不够。我们需要构建数组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的“最小绝对和”是P中两个元素之间的最小绝对差异。因此，我们只需.sort() P，并循环遍历获取每次2个相邻元素。通过这种方式，我们可以得到O（N + Nlog（N）+ N），等于O（Nlog（N））。

就这样！

- Seif

---

我很好奇你是如何实现的。 - Maresh

我用Python实现了它，但是我不再拥有代码了...你最感兴趣的部分是什么？我可以解释得更详细一些。 - Seif

这个数组[-5,8,-1]怎么样？P是[0，-5，3，2]，所以P元素之间的最小绝对差为1（2,3），但A的最小绝对和为2（-5,8,-1）。或者这个：[14，-4，5]，它给出了P [0，12，10，15]，因此P的最小差为2（10,12），但A的最小差为1（-4,5）。 - Benubird

你在第一个例子中是正确的。但对于[14，-4，5]，您错误地构建了P，它应该是[0，14，10，15]，这将给出最小差1。您能否寻找一个完全可行的解决方案？ - Seif

谢谢回复。然而，这对于100%的情况都失败了。我很好奇他们使用DP的具体答案，但是理解它需要太多时间（因为我只是出于兴趣进行测试）。所以我只是将解决方案转换成了Java。 - Soley

Answer 4

答案是肯定的，Kadane算法绝对是解决你的问题的方法。详情请参考最大子段和问题。此回答来源于我与一位博士生密切合作，他的整个博士论文都致力于研究最大子段和问题。

- wookie919

Answer 5

简短、简洁，像魔法一样好用。JavaScript/NodeJs解决方案

 function solution(A, i=0, sum =0 ) {

    //Edge case if Array is empty
    if(A.length == 0) return 0;

    // Base case. For last Array element , add and substart from sum
    //  and find min of their absolute value
    if(A.length -1 === i){
        return Math.min( Math.abs(sum + A[i]), Math.abs(sum - A[i])) ;
    }

    // Absolute value by adding the elem with the sum.
    // And recusrively move to next elem
    let plus = Math.abs(solution(A, i+1, sum+A[i]));

    // Absolute value by substracting the elem from the sum
    let minus = Math.abs(solution(A, i+1, sum-A[i]));
    return Math.min(plus, minus);
}

console.log(solution([-100, 3, 2, 4]))

- sapy

Answer 6

def min_abs_subarray(a):
    s = [a[0]]
    for e in a[1:]:
        s.append(s[-1] + e)
    s = sorted(s)
    min = abs(s[0])
    t = s[0]
    for x in s[1:]:
        cur = abs(x)
        min = cur if cur < min else min
        cur = abs(t-x)
        min = cur if cur < min else min
        t = x
    return min

- Oleg

Answer 7

这是一个Python中的迭代解决方案。它是100%正确的。

 def solution(A):
    memo = []
    if not len(A):
        return 0

    for ind, val in enumerate(A):
        if ind == 0:
            memo.append([val, -1*val])
        else:
            newElem = []
            for i in memo[ind - 1]:
                newElem.append(i+val)
                newElem.append(i-val)
            memo.append(newElem)
    return min(abs(n) for n in memo.pop())

- sapy

Answer 8

你可以运行Kadane算法两次（或在一次中完成），以找到最小和最大总和，其中找到最小值的方式与找到最大值的方式相同，只是反向符号，然后通过比较它们的绝对值来计算新的最大值。

来源-本站某人（不记得是谁）的评论。

- monster

Answer 9

public static int solution(int[] A) {
    int minTillHere = A[0];
    int absMinTillHere = A[0];
    int minSoFar = A[0];
    int i;
    for(i = 1; i < A.length; i++){
        absMinTillHere = Math.min(Math.abs(A[i]),Math.abs(minTillHere + A[i]));
        minTillHere = Math.min(A[i], minTillHere + A[i]);
        minSoFar = Math.min(Math.abs(minSoFar), absMinTillHere);
        }
    return minSoFar;
}

- Kovalan V

Answer 10

int main()
{
int n; cin >> n;

vector<int>a(n);

for(int i = 0; i < n; i++) cin >> a[i];

long long local_min = 0, global_min = LLONG_MAX;
for(int i = 0; i < n; i++)
{
    if(abs(local_min + a[i]) > abs(a[i]))
    {
        local_min = a[i];
    }
    else local_min += a[i];

    global_min = min(global_min, abs(local_min));
}
cout << global_min << endl;

}

- mayank bharati