Максимизируйте сумму элементов arr[i], выбранных путем перехода индекса по значению i

Опубликовано: 21 Сентября, 2022

Учитывая массив arr[] , задача состоит в том, чтобы вычислить максимальную сумму элементов из массива таким образом, что если выбран i -й элемент, то arr[i] добавляется к сумме, и i прыжков выполняются вперед от текущего индекса .

Примеры :

Input: N = 5, arr[] = {7, 3, 1, 2, 3}
Output: 7
Explanation:   
 

  1. Take the first element 7 to our score, then we move 7 index ahead and goes out of the array so the final answer is 7.
  2. Start from 2nd element 3 and add it to the score, then move 3 indices ahead and land on the last index of the array and add it to our score, so the final score will be 3+3=6.
  3. Start from 3rd element 1 and add to our score then move 1 index ahead and add 2 to our score, so the final score is =1+2=3.
  4. Start from 4th element 2 and add it to the score and move 2 indices ahead as we reach out of the array, the final score is 2.
  5. Start from 5th element 3 and add it to our score and our final score will be 3.

So from all the cases, the maximum score is 7.

 
 

Input: N = 2, arr[] = {3, 1}
Output: 3

 

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

  • Создайте контейнер Dp того же размера, что и массив, и переменную ans .
  • Теперь назначьте dp[n-1] как arr[n-1] , потому что максимальная сумма по этому индексу равна a[n-1] .
  • Повторить цикл в обратном направлении от n-2 до 0.
  • Для каждого индекса добавьте arr[i] к dp и проверьте
    • если i+arr[i] меньше размера массива
      • если да, добавьте dp[i+arr[i]] к dp[i].
  • Переберите массив dp, найдите максимум dp и сохраните его в нашей переменной ans.
  • Наконец, напечатайте ответ.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ