CODEWITHSUNDEEP
algorithmmathematical-optimization
hytriutucx
hytriutucx

Reputation: 1634

Maximize the sum of product of adjacent numbers

Here is a question that I encountered during an Interviewstreet codesprint. I was unable to find a a solution or even think in its direction. I'd be thankful if someone could help me find the soultion, or explain me how the problem neeeds to be dealt with.

Given numbers 1, 2, 3, .., N, arrange them in a order such that the sum of product of adjecent numbers is maximized.

For example: if N = 3, and we order them as ( 1, 2, 3 ), the sum of products is 1*2 + 2*3 = 8 and if we order them as ( 1, 3 ,2 ) the sum of products is 1*3 + 3*2 = 9.

Input format :

First line of the input contains T, the number of test-cases. Then follow T lines, each containing an integer N.

Output format :

For each test case print the maximum sum of product of adjacent numbers.

Sample input :

2 2 4

Sample output :

2 23

Explanation :

In first test case given permutation is ( 1, 2 ). So maximum sum of product is 1*2. In Second test case the numbers are (1,2,3,4). Arrangement 1,3,4,2 has sum of product of adjacent numbers as 1*3+3*4+4*2 = 23. No other arrange has sum of product of adjacent numbers more than 23.

Constraints :

1 <= T <= 10 1 <= N <= 200000

Upvotes: 2

Views: 6924

Answers (3)

Dave
Dave

Reputation: 9085

This is OEIS A101986, and can be solved in constant time.

a(n) = n*(2n^2 + 9n + 1)/6.

Upvotes: 0

P.P
P.P

Reputation: 121407

  1. Sort the array, call it sortedArray in ascending order.

  2. Remove max1, max2 and put them in a result list.

  3. Remove the next element and add it to the side of MAX(max1, max2).

  4. Update max1 and max2. i.e. max1 is left side and max2 is right side of the list.

  5. Repeat steps 3 & 4 until the sorted input array has elements.

Example: 

inputArray: 1,3,4,2,5

sortedArray: 1,2,3,4,5

Add 5 and 4 to the list first.

result = [5, 4]

Remove 3 and add it to MAX(5,4)

result = [3, 5, 4]

Remove 2 and add it to MAX(3,4)

result = [3, 5, 4, 2]

Remove 1 and add it to MAX(3,2)

result = [1, 3, 5, 4, 2]

Upvotes: 2

Blckknght
Blckknght

Reputation: 104762

The maximum sum-of-adjacent-products comes when the largest value is in the middle of the sequence, and the successively lower values alternate to its left and right. That is, your sequence for a given value n would be [..., n-3, n-1, n, n-2, n-4, ...] (or the reverse of this, which will have the same sum of products).

So, leaving out the input-parsing bits, here's the heart of the algorithm (in Python, but easily translated to other languages):

def maximumSumOfAdjacentProducts(n):
    if n == 1: # special case needed for a one element sequence
        return 1

    sumOfProducts = n * (n-1) # this pair is the "center" of the sequence

    for i in range(n-2, 0, -1): # iterate downward from n-2 to 1
        sumOfProducts += i*(i+2) # each adjacent pair is separated by 2

    return sumOfProducts

Upvotes: 6

Related Questions