CODEWITHSUNDEEP
arraysalgorithm
urel
urel

Reputation: 3

Algorithm - Find maximum sum of two numbers in unsorted array that have a minimum distance

I'm trying to find an algorithm that finds the maximum sum of two numbers that have a minimum distance D between them.

For example, lets say we have this array of 8 numbers and the minimum distance for a sum is 2:

9 4 6 2 8 7 5 6

9 can be paired with  2, 8, 7, 5, 6
4 can be paired with  8, 7, 5, 6
6 can be paired with  7, 5, 6
2 can be paired with  9 (from the left side), 5, 6
8 can be paired with  9, 4 and 6
etc..

From this array it is obvious that the maximum possible sum is 9+8 = 17

Does anyone know of an efficient algorithm to do this, or has any idea?

I have tried an algorithm which finds the max number, compares it with every possible else, and then checks every value that does not have a minimum distance from it with every possible else...but this is very slow when the array consists of many numbers and the especially when the minimum distance is large.

Note: All numbers are positive

Thanks.

Upvotes: 0

Views: 1102

Answers (1)

interjay
interjay

Reputation: 110069

For each position in the array, find and store the maximum of the elements up to that position. This can be done in O(n) for all positions by updating the maximum in each step.

By scanning right-to-left in the same manner, find and store for each position the maximum of all elements from that position to the end.

Now for each element, array[pos] + max(max_up_to[pos-D], max_from[pos+D]) will give you the highest sum that can be generated with that element. So another O(n) pass gives you the maximum over all elements.

Total: O(n) time, O(n) space.

In fact, you don't even need the additional space: The max_from array isn't needed because it's enough to evaluate array[pos] + max_up_to[pos-D] (since each sum would otherwise be generated twice). And the max_up_to values can be generated on-the-fly as you're iterating over the array.

Upvotes: 2

Related Questions