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

Дан массив arr[] , состоящий из N целых чисел и целого числа M ( первоначально 1 ), задача состоит в том, чтобы найти максимальную сумму элементов массива, выбранных игроком A , когда два игрока A и B играют в игру оптимально в соответствии со следующими правилами:

• Игрок А начинает игру.
• При каждом удобном случае можно выбрать X элементов из начала массива, где X включительно в диапазоне [1, 2*M] , выбранном соответствующим игроком в свой ход.
• После выбора элементов массива на вышеуказанных шагах удалите эти элементы из массива и обновите значение M как максимальное из X и M .
• Описанный выше процесс будет продолжаться до тех пор, пока не будут выбраны все элементы массива.

Примеры:

Input: arr[] = {2, 7, 9, 4, 4}
Output: 10
Explanation:
Initially the array is arr[] = {2, 7, 9, 4, 4} and the value of M = 1, Below are the order of ch0osing array elements by both the players:
Player A: The number of elements can be chosen over the range [1, 2*M] i.e., [1, 2]. So, choose element {2} and remove it. Now the array modifies to {7, 9, 4, 4} and the value of M is max(M, X) = max(1, 1) = 1(X is 1).
Player B: The number of elements can be chosen over the range [1, 2*M] i.e., [1, 2]. So, choose element {7, 9} and remove it. Now the array modifies to {4, 4} and the value of M is max(M, X) = max(1, 2) = 2(X is 2).
Player A: The number of elements can be chosen over the range [1, 2*2] i.e., [1, 1]. So, choose element {4, 4} and remove it. Now the array becomes empty.

Therefore, the sum of elements chosen by the Player A is 2 + 4 + 4 = 10.

Input: arr[] = {1}
Output: 1

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

• Объявите рекурсивную функцию, скажем, recursiveChoosing(arr, start, M) , которая принимает массив параметров, начальный индекс текущего массива и начальное значение M , и выполните в этой функции следующие операции:
  • Если значение start больше N , то вернуть 0 .
  • Если значение (N – start) не превышает 2*M , то вернуть сумму элементов массива из индекса start для соответствующего счета игрока.
  • Инициализируйте maxSum как 0 , в котором хранится максимальная сумма элементов массива, выбранных Player A .
  • Найдите общую сумму элементов массива с самого начала и сохраните ее в переменной, скажем, total .
  • Переберите диапазон [1, 2*M] и выполните следующие шаги:
    • Для каждого элемента X выбирает X элементов с самого начала и рекурсивно вызывает выбор элементов из оставшихся (N – X) элементов. Пусть значение, возвращаемое этим вызовом, будет сохранено в maxSum .
    • После завершения вышеуказанного рекурсивного вызова обновите значение maxSum до максимального значения maxSum и (total – maxSum) .
  • Возвращает значение maxSum в каждом рекурсивном вызове.
• После выполнения вышеуказанных шагов выведите значение, возвращаемое функцией recursiveChoosing(arr, 0, 1) .

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

Временная сложность: O(K* ^2N ), где K превышает диапазон [1, 2*M]
Вспомогательное пространство: O(N ² )

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

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

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

Временная сложность: O(K*N ² ), где K превышает диапазон [1, 2*M]
Вспомогательное пространство: O(N ² )