CODEWITHSUNDEEP
javaalgorithm
user3096840
user3096840

Reputation: 43

Max absolute sum in a array

I am came across this question recently but didn't get any idea about solving this. Can you some one help with pseudo code.

Given an array with four integers A, B, C, D, shuffle them in some order. If the integers are unique then there are 24 shuffles. My task is get the best shuffle such that

F(S) = abs(s[0]-s[1]) + abs(s[1]-s[2])+ abs(s[2]-s[3])

is maximum

For example consider this example

A=5, B= 3, C=-1, D =5
s[0]=5, s[1]=-1, s[2]= 5, s[3] =3

will give me maximum sum which is

F[s] =14

The time and space complexity are O(1).

Upvotes: 0

Views: 1381

Answers (3)

Tanel
Tanel

Reputation: 213

If array is sorted this solution also works:

F(S)= 2*abs(s[0]-s[3]) + abs(s[1]-s[2])

where s[0]=A, s[1]=B, s[2]=C and s[3]=D.

Upvotes: 2

Peter de Rivaz
Peter de Rivaz

Reputation: 33499

Algorithm

Consider laying out your points in sorted order:

A  B  C  D

Let x be the distance AB

Let y be the distance BC

Let z be the distance CD

An order which will always give the best score is BDAC with score 2x+3y+2z.

Example

In your example, the sorted points are:

A=-1 B= 3 C=5 D=5
x=4, y=2, z=0

So the best order will be BDAC=3->5->-1->5 with score 14.

Hints towards Proof

You can prove this result be simply considering all permutations of the path between the 4 points, and computing the score in terms of x,y,z.

e.g.

ABCD -> x+y+z
ACBD -> x+3y+z
ADBC -> x+3y+2z

etc.

In any permutation, the score will use x at most twice (because A is on the end so the route can only go to or from A twice). Similarly, z is used at most twice because D is on the end. y can be used at most three times because there are three things being added.

The permutation BDAC uses x twice, z twice, and y three times so can never be beaten.

Upvotes: 4

templatetypedef
templatetypedef

Reputation: 372664

Since your array has a bounded size, any algorithm you use that terminates will have time and space complexity O(1). Therefore, the simple algorithm of "try all permutations and find the best one" will solve the problem in the appropriate time bounds. I don't mean to say that this is by any stretch of the imagination the ideal algorithm, but if all you need is something that works in time/space O(1), then you've got your answer.

Hope this helps!

Upvotes: 4

Related Questions