从数组中找到元素的最低绝对和

Question

我尝试从下面提供的Codility中了解一个问题的解决方案，对于给定的具有N个整数的数组A和来自集合{−1，1}的N个整数的序列S，我们定义val（A，S）如下：val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|（假设零个元素的总和等于零。）对于给定的数组A，我们正在寻找使val（A，S）最小的序列S。编写一个函数：class Solution { public int solution(int[] A); }在给定N个整数的数组A的情况下，对于集合{-1，1}中N个整数的所有可能序列S，从val（A，S）的所有可能值中计算val（A，S）的最小值。例如，给定数组：  A[0] =  1  A[1] =  5  A[2] =  2  A[3] = -2您的函数应返回0，因为对于S = [−1，1，--1，1]，val（A，S）= 0，这是可能的最小值。假使，假设：N is an integer within the range [0..20,000];each element of array A is an integer within the range [−100..100].Complexity:预期的最坏情况时间复杂度为O（N * max（abs（A））2）; 预期的最坏情况下的空间复杂度为O（N + sum（abs（A）））（不计算输入参数所需的存储空间）。我有最近几个小时想要了解的解决方案。public static int solution(int[] A) {        int N = A.length;        int sum = 0;        int max = 0;        for (int i = 0; i < N; i++) {            A[i] = Math.abs(A[i]);            sum += A[i];            max = Math.max(A[i], max);        }        int[] counts = new int[max + 1];        for (int i = 0; i < N; i++) {            counts[A[i]] += 1;        }        int[] Total = new int[sum + 1];        Arrays.fill(Total, -1);        Total[0] = 0;        // Segment I        for (int i = 1; i <= max; i++) {            if (counts[i] > 0) {                for (int j = 0; j <= sum; j++) {                    // j th index is zero or positive                    if (Total[j] >= 0) {                        Total[j] = counts[i];                    }                    // (i-j) th index is positive                    else if ((j - i) >= 0 && Total[j - i] > 0) {                        Total[j] = Total[j - i] - 1;                    }                }            }        }如果任何人都可以解释循环的最后两个部分中发生了什么，这将非常有帮助。我只想在几行文字中找到一个简短的解释。

Answer 1

为了使总和具有必需的属性，可以找到总和尽可能接近总和一半的数组A的子集。

这是一种众所周知的方法 subset sum problem，可以通过动态编程方法解决，方法是使用尺寸对应于总和的附加数组（请注意数组Total）。

请注意，问题的解决方案仅处理正数，因此您必须对其进行修改以使用负数（例如您的示例A[3] = -2）。

此代码使数组total的长度变长，sum+1并保存array中每个值的计数counts。

在第一阶段，代码将所有可能总和的非整数项填充到总表中。考虑简单的set value：count (2:3; 3:2)。
第一轮以值3,2,1,0填充条目0,2,4,6。第二轮将所有非负条目更改为三分之二，并
从非负条目构建链的递减序列（例如4--> 4+3 ->4+6）。在那之后，我们得到了总数组，[2,-1,2,1,2,1,2,1,0,1,0,-1,0]其中负条目（不可能的总和）为1,11。请注意，这种方法不存储信息-使用了哪些项目来产生所有可能的总和，因此您必须进行更多的修改。