Динамический алгоритм для нахождения максимальной суммы продуктов «доступных» чисел в массиве

Question

Мне было предложено дать динамический алгоритм , который будет принимать последовательность четного количества чисел (как положительных, так и отрицательных) и выполнить следующие:

Каждый «поворот» двух чисел выбирается для умножения. Алгоритм может получить доступ только к концу последовательности. Однако, если выбранный номер первым номером является самым левым номером, то номер второй может быть либо самым правым числом, либо новым самым левым номером (поскольку старое левое число уже было «удалено/выбрано») и наоборот , Цель программы - найти максимум всего продуктов двух чисел, выбранных в каждом раунде.

Пример:

Последовательность: {10, 4, 20, -5, 0, 7}

оптимальный результат: 7 * 10 + 0 * -5 + 4 * 20 =

Мой прогресс:

Я пытаюсь найти динамический подход без большой удачи. Я смог вывести, что программе по существу разрешено умножать конечные числа на «смежные» числа каждый раз и что целью является умножение наименьших возможных чисел на наименьшие возможные числа (в результате получается либо двойной отрицательное умножение - положительное число или наименьшее возможное число) и продолжать применять это правило каждый раз до самого конца. В противоположность этому, это правило также применяется в противоположном направлении - умножать максимально возможные числа на максимально возможные числа каждый раз. Может быть, лучший способ - применить оба метода сразу? Я не уверен, как я уже упоминал, мне не удавалось реализовать алгоритм для этой проблемы.

Answer 1

Давайте посмотрим на обоих рекурсивный и восходящий табличный подход. Первый рекурсивный:

{10, 4,20,-5, 0, 7} 

First call: 

    f(0,5) = max(f(0,3)+0*7, f(2,5)+10*4, f(1,4)+10*7) 

Let's follow one thread: 

    f(1,4) = max(f(1,2)+(-5)*0, f(3,4)+4*20, f(2,3)+4*0) 

f(1,2), f(3,4) и f(2,3) являются "базовыми" случаи и имеют прямое решение. Теперь функция может сохранить их в таблице с индексом i,j, к которой позже будут обращаться другие потоки рекурсии. Например, f(2,5) = max(f(2,3)+0*7... также нуждается в значении для f(2,3) и может избежать создания другого вызова функции, если значение уже находится в таблице. Когда возвращаются вызовы рекурсивной функции, функция может сохранить следующие значения в таблице для f(1,4), f(2,5) и f(0,3). Поскольку массив в этом примере является коротким, сокращение вызовов функций не так уж важно, но для более длинных массивов количество перекрывающихся вызовов функций (к тому же i,j) может быть намного больше, поэтому memoization может оказаться более эффективным.

Табличный подход - это то, что я пытался развернуть в другом ответе. Здесь вместо рекурсии мы полагаемся (в данном случае) на аналогичную математическую формулировку для вычисления следующих значений в таблице, опираясь на другие значения в таблице, которые уже были рассчитаны. Звезды под массивом предназначены для иллюстрации порядка, по которому мы вычисляем значения (используя две вложенные петли for). Вы можете видеть, что значения, необходимые для вычисления формулы для каждого подмножества (i,j), являются либо базовым, либо существуют ранее в порядке цикла; это: подмножество, расширенное два элемента слева, подмножество, расширенное двумя элементами справа, и подмножество, расширенное по одному элементу в каждой стороне.

Answer 2

Возможно, вы ищете динамическое программирование . Пусть A будет массив чисел, повторение этой проблемы будет

f(start,stop) = max(// last two numbers multiplied + the rest of sequence, 
        // first two numbers multiplied + the rest of sequence, 
        // first number*last number + rest of sequence ) 

F (старт, стоп), то это оптимальный результат для подпоследовательности массива, начиная с пуска, останова. Вы должны вычислить f (start, stop) для всех допустимых значений с помощью динамического программирования или memoization.

Подсказка: первая часть // last two numbers multiplied + the rest of sequence выглядит следующим образом:

f(start,stop-2) + A[stop-1]*A[stop-2] 

Answer 3

Пусть i и j представляют первые и последние индексы массива, A после предыдущего поворота. Ясно, что они должны представлять некоторое непрерывное подмножество четного размера от A. Тогда общий случай для dp[i][j] должен быть max(left, right, both), где left = A[i-2]*A[i-1] + dp[i-2][j], right = A[j+1]*A[j+2] + dp[i][j+2] и both = A[i-1]*A[j+1] + dp[i-1][j+1]; и решение равно max(A[i]*A[i+1] + dp[i][i+1]) для всех i кроме последнего.

К счастью, мы можем вычислить дп в порядке убывания, таким образом, чтобы необходимые значения, всегда представляющие большие окружающие подмножества, уже рассчитаны (звезды представляют вычисленного подмножество):

{10, 4,20,-5, 0, 7} 
    * * * * * * 
    * * * * 
    * * 
    * * * * (70) 
    * * 
     * * * * 
     * * 
      * * left = (80 + 70) 
       * * 

Answer 4

Ниже приведен фрагмент кода рекурсивного подхода.

public class TestClass { 

    public static void main(String[] args) { 
    int[] arr = {10, 4, 20, -5, 0, 7}; 
    System.out.println(findMaximumSum(arr, 0, arr.length - 1)); 
    } 

    private static int findMaximumSum(int[] arr, int start, int end) { 
    if (end - start == 1) 
     return arr[start] * arr[end]; 

    return findMaximum(
     findMaximumSum(arr, start + 2, end) + (arr[start] * arr[start + 1]), 
     findMaximumSum(arr, start + 1, end - 1) + (arr[start] * arr[end]), 
     findMaximumSum(arr, start, end - 2)+ (arr[end] * arr[end - 1]) 
     ); 
    } 

    private static int findMaximum(int x, int y, int z) { 
    return Math.max(Math.max(x, y), z); 
    } 
} 

В результате 10 * 4 + 20 * 7 + -5 * 0 = 180

и аналогично для входа {3,9,7,1,8,2} ответ 3 * 2 + 9 * 8 + 7 * 1 = 85