带阈值的最大和子序列

Question

给定一个整数数组，找到小于或等于给定阈值的子序列的最大和。

限制因素：
数组的最大大小为 10^5
如果数组中的元素为 10^9
，则最大大小阈值在 1 到 10^9

范围内

例如
输入：
1 2 4 5
10

输出：
10

在上面的例子中，数组是[1,2,4,5]，阈值是10。最大和子序列是由(1,4,5)

组成的10

import java.util.Arrays;

public class MaxSumSubsequenceWithThreshold {

    class Solution {
        int[] A;
        int threshold;
        Integer[][] dp;
        Solution(int[] A, int threshold) {
            this.A = A; this.threshold = threshold;
            dp = new Integer[A.length][threshold + 1];
        }

        int sum(int pos, int threshold) {
            if (threshold <= 0) return 0;
            if (threshold - A[pos] < 0) return dp[pos][threshold] = Integer.MIN_VALUE;
            if (dp[pos][threshold] != null) return dp[pos][threshold];
            int sum = 0;
            int max = Integer.MIN_VALUE;
            for (int i = pos + 1; i < A.length; i++) {
                sum = sum(i, threshold - A[pos]);
                max = Math.max(max, sum);
            }
            return dp[pos][threshold] = max == Integer.MIN_VALUE ? A[pos] : max + A[pos];
        }

        int solve() {
            Arrays.sort(A);
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < A.length; i++) {
                dp[i][threshold] = sum(i, threshold);
                max = Math.max(max, dp[i][threshold]);
            }
            return max;
        }

    }

    public static void main(String[] args) {
        int[] A = InputUtils.nextIntLine();
        int threshold = InputUtils.nextInt();
        System.out.println(
                new MaxSumSubsequenceWithThreshold().new Solution(A, threshold).solve()
        );
    }

}

需要帮助验证此解决方案是否正确。

有更好的解决方案吗？

Answer 1

为了获得更好的性能，我只会循环一次这些值，并会在 TreeSet.

中跟踪所有之前的总和

成为 Set 会自动消除重复的总和。例如。如果输入是 [1, 3, 4, 7]，那么当我们处理 7 时，之前看到的和将是 [1, 3, 4, 1+3, 1+4, 3+4, 1+3+4] = [1, 3, 4, 4, 5, 7, 8] = [1, 3, 4, 5, 7, 8]，其中重复的和 4 已被消除。防止冗余处理。

如果发现总和等于 threshold，我们应该停止寻找。这被称为 short-circuting。如果我们已经找到最大可能的总和，则无需继续寻找。例如。如果 threshold = 8，我们将跳过 7 值的处理，因为我们已经找到了等于 threshold 的总和，即 1+3+4 = 8.

作为 SortedSet 允许我们找到一个子集，该子集可以添加到我们正在处理的当前值中。例如。如果threshold = 10，当我们处理7时，我们寻找3潜在的short-circuit，那么只需要考虑1-[=28=范围内的先前总和]，所以我们可以调用 subSet(1, 3) 来获取这些。

虽然问题中没有明确说明，但我们会认为空 sub-sequence 有效，这意味着 0 是有效结果，否则我们找不到解决方案。此外，虽然没有明确说明，但我们将假设值不能为负数。值是否可以超过 threshold 并不重要，因为这很容易防范。

根据上述逻辑，我们不会添加超过 threshold 的总和。例如。如果 threshold = 6，当我们完成时，上面的集合将包含 [1, 3, 4, 5]。然后我们可以调用 last() 来找到最大总和。

这是所有这些的代码：

static int maxSum(int threshold, int... values) {
    TreeSet<Integer> sums = new TreeSet<>();
    for (int value : values) {
        if (value == threshold)
            return threshold; // short-circuit
        if (value < threshold) {
            if (sums.contains(threshold - value))
                return threshold; // short-circuit
            for (int prevSum : sums.subSet(1, threshold - value).toArray(new Integer[0]))
                sums.add(prevSum + value);
            sums.add(value);
        }
    }
    return (sums.isEmpty() ? 0 : sums.last().intValue());
}

^{注意：我们不能在迭代子集的同时添加到sums，所以我们需要一个子集的副本。 toArray() 是获得此类副本的最快方法。}

测试

System.out.println(maxSum(10, 1,2,4,5));
System.out.println(maxSum(8, 1,3,4,7));
System.out.println(maxSum(10, 1,3,4,7));
System.out.println(maxSum(6, 1,3,4,7));
System.out.println(maxSum(3, 5,7,9));

输出

带阈值的最大和子序列

Max Sum Subsequence with Threshold

java

arrays

algorithm

recursion

dynamic-programming