Maximizing count of distinct numbers that produce a given sum 'k'

Question

I need help with this dynamic programming problem.

Given a positive integer k, find the maximum number of distinct positive integers that sum to k. For example, 6 = 1 + 2 + 3 so the answer would be 3, as opposed to 5 + 1 or 4 + 2 which would be 2.

The first thing I think of is that I have to find a subproblem. So to find the max sum for k, we need to find the max sum for the values less than k. So we have to iterate through the values 1 -> k and find the max sum for those values.

What confuses me is how to make a formula. We can define M(j) as the maximum number of distinct values that sum to j, but how do I actually write the formula for it?

Is my logic for what I have so far correct, and can someone explain how to work through this step by step?

Answer 1

No dynamic programming is need. Let's start with an example:

50 = 50
50 = 1 + 49
50 = 1 + 2 + 47  (three numbers)
50 = 1 + 2 + 3 + 44  (four numbers)
50 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 14  (nine numbers)

Nine numbers is as far as we can go. If we use ten numbers, the sum would be at least 1 + 2 + 3 + ... + 10 = 55, which is greater than 50 - thus it is impossible.

Indeed, if we use exactly n distinct positive integers, then the lowest number with such a sum is 1+2+...+n = n(n+1)/2. By solving the quadratic, we have that M(k) is approximately sqrt(2k).

Thus the algorithm is to take the number k, subtract 1, 2, 3, etc. until we can't anymore, then decrement by 1. Algorithm in C:

int M(int k) {
    int i;
    for (i = 1; ; i++) {
        if (k < i) return i - 1;
        else k -= i;
    }
}

Answer 2

The other answers correctly deduce that the problem essentially is this summation:

However this can actually be simplified to

In code this looks like : floor(sqrt(2.0 * k + 1.0/4) - 1.0/2)

The disadvantage of this answer is that it requires you to deal with floating point numbers.

^{Brian M. Scott (https://math.stackexchange.com/users/12042/brian-m-scott), Given a positive integer, find the maximum distinct positive integers that can form its sum, URL (version: 2012-03-22): https://math.stackexchange.com/q/123128}