Max Sum Subsequence with Threshold

Given an array of Integers find the Max Sum of Subsequence which is less than or equal to given Threshold.

Constrants:
Max size of Array is 10^5
Max size if element in array is 10^9
Threshold is in range of 1 to 10^9

e.g.
Input:
1 2 4 5
10

Output:
10

In above example array is [ 1, 2, 4, 5 ] and threshold is 10. Max sum subsequence is 10 formed by (1, 4, 5)

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

Need help in verifying if this solution is correct.

Any better solution ?

For better performance, I would only loop through the values once, and would keep track of all previous sums in a TreeSet.

Being a Set automatically eliminates duplicate sums. E.g. if input is [1, 3, 4, 7], then by the time we process 7, the sums previously seen will be [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], where the duplicate sum 4 has been eliminated. Prevents redundant processing.

We should stop looking if we find a sum equal to threshold. This is known as short-circuting. No need to keep looking if we found the max possible sum already. E.g. if threshold = 8, we would skip the processing of the 7 value, since we already found a sum equal to threshold, i.e. 1+3+4 = 8.

Being a SortedSet allows us to find a subset that can be added to the current value we're processing. E.g. if threshold = 10, when we process 7 we look for 3 for potential short-circuit, then only need to consider previous sums in range 1-2, so we can call subSet(1, 3) to get those.

Although not explicitly stated in the question, we would consider the empty sub-sequence valid, which means that 0 is a valid result, if we otherwise don't find a solution. Also, while not explicitly stated, we will assume that values cannot be negative. Whether values can exceed threshold doesn't matter much, since that's easy to guard against.

With the above logic we wouldn't add sums that exceed threshold. E.g. if threshold = 6, the above set would contain [1, 3, 4, 5], when we are done. We can then call last() to find the max sum.

Here is the code for all of that:

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

^{Note: We can't add to sums while iterating the subset, so we need a copy of the subset. toArray() is the fastest way to get such a copy.}

Tests

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

Output

10
8
10
5
0