时间戳

首页 > 解决方案 > MinAbsSum：给定整数数组，找到元素的最低绝对和

java - MinAbsSum：给定整数数组，找到元素的最低绝对和

问题描述

我遇到了想要解决的 Codility 中的一个问题，并且还收集了该问题的解决方案。问题如下，

对于给定的包含 N 个整数的数组 A 和来自集合 {−1, 1} 的包含 N 个整数的序列 S，我们将 val(A, S) 定义如下：

val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|

（假设零元素之和等于零。）

对于给定的数组 A，我们正在寻找这样一个序列 S，它使 val(A,S) 最小化。

写一个函数：

类解决方案{公共int解决方案（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 是 [0..20,000] 范围内的整数；数组 A 的每个元素都是 [−100..100] 范围内的整数。

我有下面的解决方案，

public static int solution(int[] A) {

    int N = A.length;

    if (N == 0) {
        return 0;
    }

    int sum = 0;
    int max = Integer.MIN_VALUE;

    for (int i = 0; i < N; i++) {

        int value = Math.abs(A[i]);
        sum += value;

        if (max < value) {
            max = value;
        }

        A[i] = value;
    }


    // A      = [1, 5, 2, -2]
    // A(abs) = [1, 5, 2, 2]

    // Max value = 5
    // Sum value = 10

    // counts  = [0, 1, 2, 0, 0, 1]
    int[] counts = new int[max + 1];

    for (int value : A) {
        counts[value]++;
    }

    // Total = [0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
    int[] Total = new int[sum + 1];

    for (int i = 1; i < Total.length; i++) {
        Total[i] = -1;
    }

    for (int i = 1; i < counts.length; i++) {

        for (int j = 0; j < Total.length; j++) {

            if (Total[j] >= 0) {
                Total[j] = counts[i];
            } else if (j - i >= 0 && Total[j - i] > 0) {
                Total[j] = Total[j - i] - 1;
            }
        }
    }

    int result = sum;

    for (int i = 0; i < Total.length / 2 + 1; i++) {

        if (Total[i] >= 0 && result > Math.abs(sum - 2 * i)) {
            result = Math.abs(sum - 2 * i);
        }
    }

    return result;
}

任何具有良好算法技能的人都可以向我解释解决方案吗？

标签： javaarraysalgorithmfor-loopmath

解决方案

它一个一个地遍历数组的元素。由于我们要添加连续的数字，我们需要做的就是确保总和不会变小。这就是为什么我们取一个数字并检查总和如何变化的原因。

形式上，我们可以这样写：

max(solution([a1, a2, ..., an]) = sum(abs(a1), abs(a2), ..., abs(an)),

其中abs表示绝对值 ( |x| = x * signum(x))。

例子：

假设我们有一个数组 [1, -2, 3]。绝对值数组将是 [1, 2, 3]。我们需要从所有组合中找到最大值：

1 + 2 + 3
1 + 2 - 3
1 - 2 + 3
...
-1 - 2 - 3

显然因为每个元素前面的符号不影响求和，所以我们需要考虑，如果sum + element或sum - element大于。最大的是绝对值之和：1 + 2 + 3。

推荐阅读