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

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的子集。这是一种众所周知的方法&nbsp;subset sum problem，可以通过动态编程方法解决，方法是使用尺寸对应于总和的附加数组（请注意数组Total）。请注意，问题的解决方案仅处理正数，因此您必须对其进行修改以使用负数（例如您的示例A[3] = -2）。此代码使数组total的长度变长，sum+1并保存array中每个值的计数counts。在第一阶段，代码将所有可能总和的非整数项填充到总表中。考虑简单的set value：count&nbsp;(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。请注意，这种方法不存储信息-使用了哪些项目来产生所有可能的总和，因此您必须进行更多的修改。