Максимизируйте счет, умножая элементы заданного массива на заданные множители.

Даны два массива array[] и multipliers[] размера N и M , где N всегда больше, чем равно M. Необходимо выполнить M операций. В каждой операции выберите multiplier[i] и элемент из массива arr[] либо с начала, либо с конца, скажем, K , затем добавьте multiplier[i]*K к общему счету, скажем, ans , и удалите K из массива arr[ ]. Задача состоит в том, чтобы найти максимальное значение итогового балла .

Примеры:

Input: array[] = {1, 2, 3}, multipliers[] = {3, 2, 1}, N=3, M=3
Output: 14
Explanation: An optimal solution is as follows:
– Choose from the end, [1, 2, 3], adding 3 * 3 = 9 to the score.
– Choose from the end, [1, 2], adding 2 * 2 = 4 to the score.
– Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

Input: array[] = {2, 1}, multipliers[] = {0}, N=2, M=1
Output: 0
Explanation: No matter 2 or 1 is chosen, the answer will be 0 because multiplier[0] equals 0.

Наивный подход: решение грубой силы состоит в том, чтобы рекурсивно проверить каждую пару и найти оптимальное решение.

Ниже приведена реализация вышеуказанного подхода

Временная сложность: O( ^2M )
Вспомогательное пространство: O(1)

Эффективный подход: решение основано на динамическом программировании, поскольку оно содержит как свойства — оптимальную подструктуру, так и перекрывающиеся подзадачи. Предположим, что dp[i][j] — текущий максимальный результат, который можно получить из подмассива, где i — начальный индекс, а j — конечный. На любом этапе есть два варианта:

pick the first: dp[i + 1][j] + curr_weight * array[i]

pick the last: dp[i][j – 1] + curr_weight * array[j]

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

• Инициализируйте переменную, оставшуюся как NM .
• Инициализируйте массив dp[] размера M+1 со значениями 0.
• Переберите диапазон [0, M), используя переменную i , и выполните следующие шаги:
  • Инициализируйте переменную mm как multipliers[-i-1] .
  • Переберите диапазон [0, Mi), используя переменную j , и выполните следующие шаги:
    • Установите значение dp[j] как максимальное из mm*array[j] + dp[j+1] или mm*array[j+remain] + dp[j].
    • Увеличьте значение остатка на 1.
• После выполнения вышеуказанных шагов выведите значение dp[0] в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M*M)
Вспомогательное пространство: O(M)