Maximum sum of a subsequence having difference between their indices equal to the difference between their values

Maximum sum of a subsequence having difference between their indices equal to the difference between their values

Given an array A[] of size N, the task is to find the maximum sum of a subsequence such that for each pair present in the subsequence, the difference between their indices in the original array is equal to the difference between their values.

Examples:

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 

Approach: For two elements having indices i and j, and values A[i] and A[j], if i – j is equal to A[i] – A[j], then A[i] – i is equal to A[j] – j. Therefore, the valid subsequence will have the same value of A[i] – i. Follow the steps below to solve the problem:

• Initialize a variable, say ans as 0, to store the maximum sum of a required subsequence possible.
• Initialize a map, say mp, to store the value for each A[i] – i.
• Iterate in the range [0, N – 1] using a variable, say i: 
  • Add A[i] to mp[A[i] – i].
  • Update ans as the maximum of ans and mp[A[i] – i].
• Finally, print ans.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void maximumSubsequenceSum(int A[], int N) {          int ans = 0;             map<int, int> mp;             for (int i = 0; i < N; i++) {                     mp[A[i] - i] += A[i];                     ans = max(ans, mp[A[i] - i]);     }             cout << ans << endl; }    int main() {          int A[] = { 10, 7, 1, 9, 10, 1 };     int N = sizeof(A) / sizeof(A[0]);             maximumSubsequenceSum(A, N);     return 0; }

Output:

26

Time Complexity: O(N)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with industry experts, please refer Geeks Classes Live 

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets