CODEWITHSUNDEEP
arraysalgorithmdynamic-programming
23thMay
23thMay

Reputation: 51

Pick numbers to maximize interval

There is an array that contains a number from 0 to 999 in strictly increasing order.

For example 

int[] array = {0, 24, 55, 124, 200, 259, 400, 503, 666, 797};

What I have to do is implement a function that picks N numbers so that the minimum value of distances between those picked numbers is maximized.

For example, if N is 3, then the picked numbers are 0, 400, 797 and the intervals are 400 and 397; so the return value is 397 (which should be maximized). If we pick other sets of numbers, then the return value would be less than (or equal to) 397.

I'd like to implement it using recursion, but I'm having a hard time coding it. Would you like to help me?

Upvotes: 4

Views: 501

Answers (1)

Nemanja Trifunovic
Nemanja Trifunovic

Reputation: 3105

This problem can be solved using dynamic programing.

If we define s[c][p] to be the solution when picking c numbers and the last chosen number has index p in the input array.

We can then calculate s[c][p] as max for i=0..p of max(s[c-1][p-i], array[p] - array[p-i])

At the beginning following states: s[1][0..n], where n is the length of the input array, should have value 0.

Having s[1][0..n] we can now easily calculate s[2][0..n], using given formula.
Having s[2][0..n] we can now easily calculate s[3][0..n].
And so on ...

The solution to the entire problem would be max s[N][N-1..n] where n is the length of the input array and N is number of numbers to choose.

The time complexity of this solution is O(N*n^2).
Explanation: We calculate values for s[0..N][0..n] where each calculation has time complexity of O(n).

The memory complexity of this solution is O(n).
Explanation: to calculate s[c][0..n] you only need s[c-1][0..n] so only 2*n of the memory is actually needed in every point in time.

EDIT: You can use recursion to implement described algorithm, using programming technique called memoization (https://en.wikipedia.org/wiki/Memoization).

Upvotes: 2

Related Questions