CODEWITHSUNDEEP
clogic
kidchicken
kidchicken

Reputation: 11

Need some simple logic help, been stuck for a few hours

The problem is asking to take any amount of numbers, and find the highest possible sum of difference(using absolute value) between consecutive numbers. For example numbers 1 2 and 3 would be arranged 3 1 2 to get a sum of 3 (3-1 = 2, and 1-2 = 1).

Now my first thoughts were to take the highest number in the list followed by the lowest number and arrange in that way through the end, but that doesnt work out as the end of the list will end up having all of the numbers in the middle accumulating almost no differences. The only other thing I have thought of is to find every single possible order and return the highest sum, but with a longer list this will take way too long and I assume there might be a better way.

For reference here are some sample input and output numbers

9 2 5 3 1  ->  21
7 3 4 5 5 7 6 8 5 4 -> 24

Any help at all would be much appreciated, even if its just pointing me in the right direction.

Upvotes: 1

Views: 74

Answers (1)

Klas Lindbäck
Klas Lindbäck

Reputation: 33273

There are 2 approaches to this problem.

Approach 1:

Brute force.

Approach 2:

Figure out an algorithm for how to arrange the numbers.

I always like approach 2 better if it is feasible.

It seems reasonable that you would get a high sum if you order the numbers high-low-high-low-high...

So start by sorting the numbers and then divide them into two equally large groups of low and high numbers. If there is an odd number of numbers the middle number will be left over.

Then you just pick numbers alternately from the two groups.

It is easy to prove that the order of the interior numbers doesn't matter as long as you stick with the high-low-high-low ordering. However, since the start and end number only has one neighbour, the first and last number should be the middle numbers.

Finally, if you have an odd number of numbers, place the last number at the start or end, whatever gives the biggest difference.

Example:

7 3 4 5 5 7 6 8 5 4 -> [sort] -> 3 4 4 5 5 5 6 7 7 8 
high numbers: 5 6 7 7 8  
low numbers: 3 4 4 5 5  

Arranged:
5 3 6 4 7 4 7 5 8 5 = 24

Example:

9 2 5 3 1 -> [sort] -> 1 2 3 5 9
high numbers: 5 9
low numbers: 1 2
left over: 3

Arranged:
3 5 1 9 2 = 21       (3 goes at the start, because |3-5| > |3-2|)

Upvotes: 3

Related Questions