algorithm - Given an positive integer array, rearrange the array so that the sum of product of adjacent elements can be maximized -

interview question. looking algorithm can better o(n^2), n size of input array. (n<5000)

the questions states follows:

assume given array of positive integer (let's call a). find out way re-arrange order of these element value of following function can maximized:

obj = a[0]*a[1] + a[1]*a[2] + ... + a[n-2]*a[n-1] + a[n-1]*a[n]

in addition, there array of boolean (let's call b), has same size positive integer array. if b[k] = false, means when re-arrange element in positive array, cannot move kth elements.

---

example

a = [ 1,2,3 ], b = [ true, true, true ]

since elements of b true, can re-arrange array whatever know. there 6 ways re-array (e.g. [1,2,3], [1,3,2], [2,1,3] ....). following objective function value these 6 arrangement. arrangement maximize objective function [1,3,2] or [2,3,1] since:

1 * 3 + 3 * 2 = 9

2 * 3 + 3 * 1 = 9

another example:

a = [ 1,2,3 ], b = [ true, false, true ]

in case, integer 2 cannot moved there 2 arrangement - [1,2,3] , [3,2,1]. both of them yield same objective function value.

---

update

i used brute force method test algorithm provided @shapiro.yaacov on positive integer array distinct elements. here test run:

input: [ 1,2,4,8,16,32,64 ]

output:

obj = 3412, when [2, 8, 32, 64, 16, 4, 1] or

obj = 3412, when [1, 4, 16, 64, 32, 8, 2]

input: [1, 10, 100, 1000]

output:

obj = 110100, when [1, 100, 1000, 10] or

obj = 110100, when [10, 1000, 100, 1]

as can see, there @ least 2 arrangements can maximize objective function - 1 arrange reversed version of one.

even not requirement of question, algorithm works array 0 too. however, need come best arrangement without zero, , append 0 either side of new arrangement. example:

input: [0,1,2,4,8,16,32,64]

output:

obj = 3412, when [2, 8, 32, 64, 16, 4, 1, 0] or

obj = 3412, when [0, 2, 8, 32, 64, 16, 4, 1] or

obj = 3412, when [1, 4, 16, 64, 32, 8, 2, 0] or

obj = 3412, when [0, 1, 4, 16, 64, 32, 8, 2]

this solution o(n*logn):

take array a, , sort (possible) elements in it. possible mean who's index in b array true. step takes o(n*logn).

deprecated:
given obj function, want multiply biggest number second biggest, second third etc. optimization might done here swapping a[0] smallest number , a[1] biggest etc. (with a = [1, 2, 3, 4, 8] obj bigger). in case, since have array sorted already, step easy o(n).

edit:
given obj function, , after conversation @edward doolittle, best arrangement:

[1, ..., n-4, n-2, n, n-1, n-3, ...., 2] 

edit 2:

dealing elements can not moved: start sorting elements can sort. @ locations can go , sort locations multipliers on both sides. if optional location has 8 on 1 side , 3 on other, multiplier's value 24. assign highest value element highest value location.

can't prove right optimal, isn't far off. think.