Максимизируйте абсолютную разницу

Question

Учитывая массив монет, каждый из которых имеет какое-то значение. Размер рамки равен N. Вы можете изменить значение любой монеты, кроме первой и последней монеты. Вы можете изменить значение i-й монеты на половину суммы значения (i-1) th и (i + 1) -ой монеты, но для этого необходимо выполнить два условия.

(1) значение как (I-1) -го и (г + 1) -й монета должна быть ровной и

(2), если значение JTH монеты изменяется после того, как значение Ith монеты, то J должно быть больше чем i

Теперь ваша задача - максимизировать абсолютную разницу между суммой значений 1-й половины монет массива и значениями 2-й половины монет массива. Если размер массива нечетный, игнорируйте средний элемент.

Может ли кто-нибудь предложить мне алгоритм, чтобы найти ответ.

Задача состоит в том, чтобы найти максимальную абсолютную разницу.

Мои алго: 1. Найдите сумм левой половины и правой половины 2. если левая половина> правую половина максимально левую половину, делая операции, заданные и minize левой половины, но я не адресность правильного ответа.

PS: Я присутствовал на одном собеседовании за неделю до этого. Меня спросили, что я не могу понять этот подход.

Answer 1

Я не мог придумать более сложный алгоритм, чем грубую силу. Вы просто должны попробовать все возможные вещи и вернуть лучший результат. Я рекомендую рекурсивный подход. Напишите рекурсивную функцию, которая принимает входной список и индекс в качестве параметров. Функция пытается изменить число, находящееся на этом индексе, и вернет лучший результат. В конце вы должны напечатать лучший результат. Это звучит сложно, но в действии это довольно легко. Посмотрите на этот код:

def func(input_list, index): 
    # if we have reached the end of the list 
    # we compute the result and return it 
    L = input_list[:] 
    if index == len(L): 
    # return absolute difference of the two halves 
     return abs (sum(L[:len(L)/2]) - sum(L[int(len(L)/2.0 + 1):])) 

    #result of not changing this item 
    no_change = func(L, index+1) 

    #check if it is possible to change this item 
    change = 0 
    if index-1 >= 0 and index+1 < len(L) and L[index-1]%2==0 and L[index+1]%2==0: 
     #result of changing this item if possible 
     L[index] = (L[index-1] + L[index+1])/2 
     change = func(L, index+1) 

    #return the maximum result of changing and not changing 
    best = max(no_change, change) 
    return best 


L = [10, 4, 22, 8, 64] 
print func(L, 0) 

который печатает

93 

Окончательный список [10, 4, 22, 43, 64]

Но имейте в виду, что этот метод неэффективен и не будет работать для больших входов ,

Answer 2

Возможны некоторые оптимизации по алгоритму грубой силы.

Мы могли бы заставить алгоритм хранить по каждому индексу возможные суммы, рассчитанные из всех данных, которые следует справа. Эта информация будет заполнена во время отступления от рекурсии.

Пример: для упрощения рассмотрю только максимизацию суммы первой половины и минимизацию суммы второй половины.

[4, 1, 8, 2, 4, 1, 4] 

алгоритм будет идти в глубину в сторону последнего элемента массива, а затем сохранить лучшую сумму там, только с учетом того, что следует справа. Поскольку ничего нет, сумма равна 4. Но поскольку мы хотим минимизировать, мы переключаем знак. Поэтому мы храним что-то вроде этого:

[4, 1, 8, 2, 4, 1, 4] 
        -4 

Тогда мы возвращаемся. Там у нас есть две возможности: мы оставляем 1 as-is или используем среднее значение окружающих значений (т.4):

[4, 1, 8, 2, 4, 1, 4] 
        -4 
       -5 
[4, 1, 8, 2, 4, 4, 4] 
        -4 
       -8 

Оба значения -5 и -8 будут храниться в хэш, так что для значения 1 можно найти -5, и значение 4 можно найти -8.

В какой-то момент в алгоритме мы попробуем со значением 6 во втором элементе массива (вместо 1), а затем снова рекурсивно. Когда мы приходим к одному, но последнему элементу, мы обнаруживаем, что возможные значения снова 1 или 4 (если ничего не было изменено с левой стороны), и поэтому нам не нужно регрессировать глубже: мы можем прочитать суммы из хеша, которые мы поддерживаем при этом индексе.

Эта система может принести большую экономию в больших массивах, следя за тем, чтобы алгоритм только углублялся в рекурсию, когда это действительно необходимо. Очевидно, что это связано с затратами с точки зрения пространства.

Затем весь алгоритм может быть выполнен второй раз, но затем заменяется знаком. Из этих двух результатов достигается наилучшее решение, максимизирующее абсолютную величину.

Передавая значение измененного элемента в качестве аргумента функции, мы можем избежать создания нескольких массивов и просто работать с входным массивом. С другой стороны, хэш - созданный при каждом индексе - занимает некоторое пространство.

Вот алгоритм в JavaScript, в котором я не использовал никаких замысловатых ухищрений, поэтому она должна быть легко следовать:

function getMaxSum(a) { 
 
    // Index of the element in the middle. If integer, 
 
    // the element at this index will not play a role in any sum: 
 
    var mid = (a.length-1)/2; 
 
    // Two results, one that maximises the left sum and minimises the right sum 
 
    // The other minimises the left and maximises the right: 
 
    var result, result2, b; 
 

 
    function recurse(prevVal, index, sign, hash = []) { 
 
     var val, nextVal, sum, result, avg; 
 
     
 
     val = a[index]; 
 
     if (index >= a.length-1) { 
 
      // At the last element there are no choices left: 
 
      return { sum: -sign*(prevVal+val), nextVal: val, hash: [] }; 
 
     } 
 
     if (!hash[index]) hash[index] = []; 
 
     nextVal = a[index+1]; 
 
     result = { sum: -Infinity, nextVal: 0, hash: hash[index] }; 
 
     // Loop through the 2 possibilities (in general): take value as is, or 
 
     // take the average of previous and next value: 
 
     while (true) { 
 
      // If the result from this position onward is not know, calculate 
 
      // it via a recursive call: 
 
      if (!hash[index][val]) hash[index][val] = recurse(val, index+1, sign, hash); 
 
      // Add the previous value to the best sum at this point, using the appropriate sign, 
 
      // and store the result in a hash table, for future reference: 
 
      sum = hash[index][val].sum + (index-1 > mid ? -1 : index-1 < mid ? 1 : 0) * sign * prevVal; 
 
      if (sum > result.sum) { 
 
       result.sum = sum; 
 
       result.nextVal = val; 
 
      } 
 
      if (prevVal % 2 || nextVal % 2 || (avg = (prevVal + nextVal)/2) === val) break; 
 
      val = avg; 
 
     } 
 
     return result; 
 
    } 
 

 
    // Calculate both results 
 
    result = recurse(a[0], 1, 1, []); 
 
    result2 = recurse(a[0], 1, -1, []); 
 
    // Pick the best one. 
 
    if (Math.abs(result2.sum) > Math.abs(result.sum)) result = result2; 
 

 
    // Rebuild the array corresponding to the best result: 
 
    b = [a[0]]; 
 
    while (result) { 
 
     b.push(result.nextVal); 
 
     result = result.hash[result.nextVal]; 
 
    } 
 
    return b; 
 
} 
 

 
// Sample data 
 
var a = [4, 1, 8, 2, 4, 1, 4]; 
 
console.log(' input: ' + a); 
 
// Apply algorithm 
 
var b = getMaxSum(a, 1); 
 
// Print result 
 
console.log('result: ' + b);