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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// a subsequence having difference between// indices equal to difference in their valuesvoid maximumSubsequenceSum(int A[], int N){ // Stores the maximum sum int ans = 0; // Stores the value for each A[i] - i map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) { // Update the value in map mp[A[i] - i] += A[i]; // Update the answer ans = max(ans, mp[A[i] - i]); } // Finally, print the answer cout << ans << endl;}// Driver Codeint main(){ // Given Input int A[] = { 10, 7, 1, 9, 10, 1 }; int N = sizeof(A) / sizeof(A[0]); // Function Call maximumSubsequenceSum(A, N); return 0;} |
Java
// Java program for the above approachimport java.util.HashMap;public class GFG{ // Function to find the maximum sum of // a subsequence having difference between // indices equal to difference in their values static void maximumSubsequenceSum(int A[], int N) { // Stores the maximum sum int ans = 0; // Stores the value for each A[i] - i HashMap<Integer, Integer> mp = new HashMap<>(); // Traverse the array for (int i = 0; i < N; i++) { // Update the value in map mp.put(A[i] - i, mp.getOrDefault(A[i] - i, 0) + A[i]); // Update the answer ans = Math.max(ans, mp.get(A[i] - i)); } // Finally, print the answer System.out.println(ans); } // Driver code public static void main(String[] args) { // Given Input int A[] = { 10, 7, 1, 9, 10, 1 }; int N = A.length; // Function Call maximumSubsequenceSum(A, N); }}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach# Function to find the maximum sum of# a subsequence having difference between# indices equal to difference in their valuesdef maximumSubsequenceSum(A, N): # Stores the maximum sum ans = 0 # Stores the value for each A[i] - i mp = {} # Traverse the array for i in range(N): if (A[i] - i in mp): # Update the value in map mp[A[i] - i] += A[i] else: mp[A[i] - i] = A[i] # Update the answer ans = max(ans, mp[A[i] - i]) # Finally, print the answer print(ans)# Driver Codeif __name__ == '__main__': # Given Input A = [ 10, 7, 1, 9, 10, 1 ] N = len(A) # Function Call maximumSubsequenceSum(A, N)# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System.Collections.Generic; using System; class GFG{// Function to find the maximum sum of// a subsequence having difference between// indices equal to difference in their valuesstatic void maximumSubsequenceSum(int []A, int N){ // Stores the maximum sum int ans = 0; // Stores the value for each A[i] - i Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for(int i = 0; i < N; i++) { // Update the value in map if (mp.ContainsKey(A[i] - i)) mp[A[i] - i] += A[i]; else mp[A[i] - i] = A[i]; // Update the answer ans = Math.Max(ans, mp[A[i] - i]); } // Finally, print the answer Console.Write(ans);}// Driver codepublic static void Main(String[] args){ // Given Input int []A = { 10, 7, 1, 9, 10, 1 }; int N = A.Length; // Function Call maximumSubsequenceSum(A, N);}}// This code is contributed by amreshkumar3 |
Javascript
<script>// javascript program for the above approach// Function to find the maximum sum of// a subsequence having difference between// indices equal to difference in their valuesfunction maximumSubsequenceSum(A, N){ // Stores the maximum sum var ans = 0; // Stores the value for each A[i] - i var mp = new Map(); var i; // Traverse the array for(i = 0; i < N; i++) { // Update the value in map if(mp.has(A[i] - i)) mp.set(A[i] - i,mp.get(A[i] - i)+A[i]); else mp.set(A[i] - i,A[i]); // Update the answer ans = Math.max(ans, mp.get(A[i] - i)); } // Finally, print the answer document.write(ans);} // Driver Code // Given Input var A = [10, 7, 1, 9, 10, 1]; var N = A.length; // Function Call maximumSubsequenceSum(A, N); </script> |
Output:
26
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
