Given an array of n integers, arr, rearrange them so that the following equation is minimized.
sigma i=0 to n-1, arr[i]*arr[i+1]
Examples: n=7 arr=1,10,2,7,10,6,6
Answer: 127 (optimal arrangement is 10,1,7,6,6,2,10)
By looking at this example it looked like just adjusting max and min elements adjacently words, but that's doesn't work for below example
example 2:
arr=2,4,10,9,3
answer: 67 (optimal arrangement: 10,2,4,3,9)
By this example looks like just put the max elements at ends and arrange min->max form borders to middle is the logic. But this again doesn't;t work for all cases. And the fact that these are integers meaning there can be negative values makes it even more harder. Help me out :)
I've tried:
Simple Greedy Approach: Initially, we attempted a greedy strategy that involved sorting the array and pairing the smallest and largest elements to calculate the product sum. This approach proved to be suboptimal as it did not always yield the minimum possible sum, particularly in cases where the largest numbers should not be paired with the smallest.
Nuanced Greedy Approach: We refined the greedy approach by placing the largest number at one end of the result array and the second-largest next to the smallest number. This strategy aimed to minimize the impact of the largest numbers by pairing them with the smallest possible counterparts. While this heuristic was more nuanced than the initial simple pairing, it still did not consistently provide the optimal solution.
If all integers are either all nonnegative or all nonpositive, be greedy from both ends at once.
Repeat until you're done.
E.g. 1,10,2,7,10,6,6
10, ..., 10
10, 1, ..., 2, 10
10, 1, 7, ..., 6, 2, 10
10, 1, 7, 6, 6, 2, 10; sumproduct is 10+7+42+36+12+20 = 127
The idea here is to have large numbers next to small numbers. The reason for starting with large numbers at both ends is that those indices only get multiplied once.
If the numbers are mixed, so there are some positive and some negative, then we want to maximize the magnitude of negative products, so we'll want large negative numbers surrounded by large positive numbers and vice versa
Case 1: The count of negatives is within one of the count of positives: We'll alternate positives and negatives, so every product is negative. Then, we want to maximize the magnitude of the products, so have the endpoints be the smallest magnitude eligible pair (eligible as in matching the sign you want in those indices), then place the smallest among the remaining, and so on. For each pair, put the larger magnitude integer at the smaller index
E.g. 8, -3, 5, -12, 9: 3 positives & 2 negatives, so [+, -, +, -, +]
1) [8, ..., 5]
2) [8, -12, ..., -3, 5]
3) [8, -12, 9, -3, 5]
If positives exceed negatives by more than 1, say n negatives and p >= n+2 positives, then first form the 2n+1 subarray as above using all negatives and the n+1 largest magnitude positives. Position this at the start of the n+p array you're building to answer this question. Then, continue with the original algorithm on the remaining, positive values.
If negatives exceed positives by more than 1, say p positives and n >= p+2 negatives, then again start by forming the 2p+1 subarray using the above algorithm on the p positives and p+1 largest magnitude negatives. Position this at the start of the n+p array you're building to answer this question, then, continue with the original algorithm on the remaining, negative values, but treat all numbers as their magnitude (absolute value). We can do this because everything left is negative, so the product of each pair is positive.
E.g., 8, -3, 5, -12, 9, -2, -4, -16, -1
sorted: [-16, -12, -4, -3, -2, -1, 5, 8, 9]
all 3 positives: [5, 8, 9]
4 largest magnitude negatives: [-16, -12, -4, -3]
prev. algorithm: [-4, 5, -16, 9, -12, 8, -3]
need to use: [-1, -2]
final: [-4, 5, -16, 9, -12, 8, -3, -1, -2]