Как получить максимальную сумму массива при следующем условии? - PullRequest
Новая
       35

Как получить максимальную сумму массива при следующем условии?

0 голосов
/ 05 ноября 2018

Предположим, проблема в следующем:

На Марсе живет колония червей. Каждый червь представлен в виде элементов в одномерном массиве. Черви решают съесть друг друга, но любой червь может съесть только своего ближайшего соседа . Каждый червь имеет заранее установленное количество энергии ( т.е. значение элемента ). На Марсе законы гласят, что когда червь i с энергией x съедает другого червя с энергией y , i -го червя конечная энергия становится xy . Червю разрешено иметь отрицательные энергетические уровни.

Найдите максимальное значение энергии последнего стоящего червя. 

Sample data:
0,-1,-1,-1,-1 has answer 4.
2,1,2,1 has answer 4.

Какая логика будет подходить для решения этой проблемы?

1 Ответ

0 голосов
/ 05 ноября 2018

Эта проблема имеет удивительно простое решение O (N) .

Если любой два члена в массиве имеют разные знаки, то ответом является сумма абсолютных значений всех элементов.

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

В более общем случае, если массив размером N имеет значения разных знаков, мы всегда можем найти массив размером N-1 с разными знаками, потому что должна быть пара соседей с разными знаками, которые мы можем объединить, чтобы сформировать число любого знака, который мы предпочитаем.

Например, с этим массивом: [1,2,-5,4,-10]

  1. мы можем объединить (2, -5) или (4, -10). Позволяет объединить (4, -10), чтобы получить [1,2,-5,-14]
  2. Теперь мы можем взять только (2, -5). Итак, наш массив сейчас: [1,-7,-14]
  3. Опять только (1, -7) возможно. Но на этот раз мы должны сохранить совокупную ценность положительной. Итак, у нас осталось: [8,-14]
  4. Окончательное объединение дает нам 22, сумму всех абсолютных значений.

В случае всех значений с одним и тем же знаком нашим первым шагом будет создание противоположного знака, объединяющего пару соседей с минимально возможной «стоимостью». Интуитивно понятно, что мы не хотим тратить два больших числа на это преобразование. Если мы возьмем x,y соседнюю пару, то при объединении новое значение (с противоположным знаком) будет abs(x-y). Поскольку результат - это просто сумма абсолютных значений, мы можем интерпретировать его как - «потерять» abs(x) и abs(y) от максимально возможного выхода и вместо этого «получить» abs(x-y). Таким образом, «стоимость» использования этой пары для преобразования знака составляет abs(x)+abs(y)-abs(x-y). Поскольку нам нужно минимизировать эту стоимость, мы выбираем из исходной пары соседей массива, которые имеют наименьшее такое значение.

Итак, если мы возьмем вышеуказанный массив, но теперь все значения положительны [1,2,5,4,10]:

  1. "стоимость" конвертации (1,2) в -1 равна 1+2-abs(-1)=2.
  2. "стоимость" конвертации (2,5) в -3 равна 2+5-abs(-3)=4.
  3. "стоимость" конвертации (5,4) в -1 равна 5+4-abs(-1)=8.
  4. "стоимость" конвертации (4,10) в -6 равна 4+10-abs(-6)=8.

Итак, мы берем и конвертируем пару (1,2) в -1. Затем просто сложите абсолютные значения результирующего массива, чтобы получить 20. Обратите внимание, что это значение ровно на 2 меньше, чем в нашем предыдущем примере.

...