Maximum sum of a subsequence having difference between their indices equal to the difference between their values | C ++ program for the above approach ; Function to find the maximum sum of a subsequence having difference between indices equal to difference in their values ; Stores the maximum sum ; Stores the value for each A [ i ] - i ; Traverse the array ; Update the value in map ; Update the answer ; Finally , print the answer ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE 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 ; }