How to find minimum pairing cost? (Any Language)-CodePudding

I came across an algorithm question recently and I still haven't been able to come up with a way to solve it. Can anyone help with pseudocode or logic?

Here is the question: There are n elements in the array. N is an odd number. When we exclude 1 element from array, we are finding the minimum pairing cost.

Rules:

1 <= n <= 1001

n % 2 = 1

Example:

Given array is [4, 2, 1, 7, 8]

When we pair items with the closest ones [[1,2], [7,8]] and "4" is excluded. So the minimum cost is |1 - 2| |7 - 8| = 2;

What i tried:

Sort array first: [1,2,4,7,8]
Remove the middle element: 4
Pair items with the next ones: [[1, 2], [7, 8]]

According the example it works but what if the given array is [1, 7, 8, 16, 17]?

Sort array first: [1, 7, 8, 16, 17]
Remove the middle element: 8
Pair items with the next ones: [[1, 7], [16, 17]] Wrong Answer
"1" must be excluded and the pairs must be [[7, 8], [16, 17]]

CodePudding user response：

Sorting the array first is a good start. Once you've done that, you have a choice of removing any value from index 1..N. A brute-force approach would be to calculate the pairing cost of omitting index 1, then recalculate omitting only index 2, and so on until you reach index N.

You'd be calculating many of the pairs over and over. To avoid that, consider that all the pairs to the left of your omitted index are paired odd-even (from the perspective of starting at element 1) and to the right of the omitted index will be even-odd. If you precalculate the sums of the left pairings and the sums of the right pairings into two arrays, you could determine the minimum cost at each position as the minimum sum of both values at each position of those two arrays.

CodePudding user response：

Once the array is sorted, you can pair all elements from left to right, keep track of the total sum, and replace the last pairing with one starting from the right, updating the total sum if it's smaller.

In pseudo-code (all zero-based indexing):

let S be the sum of all pairing costs of
elements 2i and 2i 1 for i from 0 to (n-3)/2
(that is all pairings when you exclude the very last element)

let j = (n-1)/2
for i from (n-3)/2 to 0 (included):
    let L be the pairing cost of elements 2i and 2i 1
    let R be the pairing cost of elements 2i 1 and 2i 2
    let S' = S - L   R
    if S' < S
        replace S with S'
        replace j with i

2j is the element to exclude