[Algorithm] Find max U | OF学习之旅

type

status

date

slug

summary

🔎 Problem

Rearrange an array of integers so that the calculated value U is maximized. Among the arrangements that satisfy that test, choose the array with minimal ordering. The value of U for an array with n elements is calculated as :

U = arr[1]×arr[2]×(1÷arr[3])×arr[4]×...×arr[n-1] × (1÷arr[n]) if n is odd or U = arr[1]×arr[2]×(1÷arr[3])×arr[4]×...×(1÷arr[n-1]) × arr[n] if n is even

The sequence of operations is the same in either case, but the length of the array, n, determines whether the calculation ends on arr[n] or (1÷arr[n]). Arrange the elements to maximize U and the items are in the numerically smallest possible order.

example_arrs = [21, 34, 5, 7, 9] result = [9, 21, 5, 34, 7] max = 183.6

📝 Critical process

According to the title, we need to reach two conditions Condition 1: Find the largest U-value Condition 2: If condition 1 is met, sort the list in the smallest order

Analyzing the equation for U shows that:

1. All elements are multiplied, so if the value of an element is fixed, changing the position of an element in the equation will not change the result.

2. From 1, the size of the result U depends on the size of the elements in the equation

3. Further, it is clear from the equation that the size of an element is determined only by its position, starting at the odd bits of the equation(from the index bit index >= 2), the element is changed to (1/element itself), and remains unchanged at the event bits, so to find the largest U, one should make the elements at these odd bits as large as possible.

4. By the nature of division, 1 / x should be as large as possible, so the base x should be as small as possible, so you should use the smallest element of the list as the x-value as much as possible

5. In analyzing the equation from the question, it is clear that the number of elements that need to be converted to their own fractions m:

m = { 0, n <=2, (n - 3) / 2 + 1 , n>2, if n is odd (n-2) / 2, n>2, if n is even }

🔎 Problem

📝 Critical process

Analyzing the equation for U shows that:

Code implementation