Максимальная сумма подпоследовательности, у которой разница между их индексами равна разнице между их значениями

Учитывая массив A[] размера N , задача состоит в том, чтобы найти максимальную сумму подпоследовательности, такую, что для каждой пары, присутствующей в подпоследовательности, разница между их индексами в исходном массиве равна разнице между их значениями.

Примеры:

Input: A[] = {10, 7, 1, 9, 10, 15}, N = 6
Output: 26
Explanation: 
Subsequence: {7, 9, 10}. 
Indices in the original array are {1, 3, 4} respectively.
Difference between their indices and values is equal for all pairs. 
Hence, the maximum possible sum = (7 + 9 + 10) = 26.

Input: A[] = {100, 2}, N = 2
Output:100 

Подход: для двух элементов, имеющих индексы i и j и значения A[i] и A[j], если i – j равно A[i] – A[j], то A[i] – i равно А[j] – j . Следовательно, допустимая подпоследовательность будет иметь то же значение A[i] – i . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем , как 0, чтобы сохранить максимально возможную сумму требуемой подпоследовательности.
• Инициализируйте карту, скажем, mp, чтобы сохранить значение для каждого A[i] – i .
• Выполните итерацию в диапазоне [0, N – 1] , используя переменную, скажем, i :
  • Добавьте A[i] к mp[A[i] – i].
  • Обновить ans как максимум ans и mp[A[i] – i].
• Наконец, напечатайте ответ .

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

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