Given an array arr[] consisting of integers of length N and an integer K (1 <= K <= N), the task is to find the maximum sub-sequence sum in the array such that adjacent elements in that sub-sequence have at most a difference of K in their indices in the original array. In other words, if i and j are indices of two consecutive elements of sub-sequence in original array then |i-j| <= K .
Examples:
Input: arr[] = {1, 2, -2, 4, 3, 1}, K = 2
Output: 11
Explanation : The sub–sequence with maximum sum is {1, 2, 4, 3, 1} (difference between indices <=2)Input: arr[] = {4, -2, -2, -1, 3, -1}, K = 2
Output: 5
Explanation : The sub-sequence with maximum sum is {4, -2, 3} (difference between indices <=2)
Naive approach: Generate all possible subsets of the array and check for each of the subsets whether it satisfies the condition such that two adjacent elements have at most difference of K in their indices. If yes, then compare its sum with the largest sum obtained till now and update the sum if it is greater than the obtained sum till now.
Efficient Approach: This problem can be solved using Dynamic Programming.
Create a table dp[], where dp[i] stores the largest possible sum for the sub-sequence till the ith index.
- If the current element is the first element of the sub-sequence then:
dp[i] =arr[i]
- Otherwise, we have to check previous results and check what is the maximum result of dp in a window of K behind this index :
dp[i] = max(arr[i] + dp[x]) where x is from [i-k, i-1]
- For every index choose that condition which gives the maximum sum at that index, So final recurrence relation will be:
dp[i] = max(arr[i], arr[i] + dp[x]) where i-k <= x <= i-1
So, for checking what is the maximum value behind this index in a window of K, either we can iterate from dp[i-1] to dp[i-k] and find the maximum value, in which case the time complexity will be O(N*K) or it can be reduced by taking an ordered map and keep maintaining the computed dp[i] values for every index. This reduces the complexity to O(N*log(K)).
Below is the implementation of the above approach.
C++
// C++ implementation to// C++ program to// find the maximum sum// subsequence such that// two adjacent element// have atmost difference// of K in their indices#include <iostream>#include <iterator>#include <map>using namespace std;int max_sum(int arr[], int N, int K){ // DP Array to store the // maximum sum obtained // till now int dp[N]; // Ordered map to store DP // values in a window ok K map<int, int> mp; // Initializing dp[0]=arr[0] dp[0] = arr[0]; // Inserting value of DP[0] // in map mp[dp[0]]++; // Initializing final answer // with dp[0] int ans = dp[0]; for (int i = 1; i < N; i++) { // when i<k there is no // need to delete elements // from map as window is // less than K if (i < K) { // Initializing iterator // to end af map auto it = mp.end(); // Decreasing iterator to // get maximum key it--; // Evaluating DP[i] // from recurrence dp[i] = max(it->first + arr[i], arr[i]); // Inserting dp value in map mp[dp[i]]++; } else { auto it = mp.end(); it--; dp[i] = max(it->first + arr[i], arr[i]); mp[dp[i]]++; // Deleting dp[i-k] from // map because window size // has become K+1 mp[dp[i - K]]--; // Erase the key from if // count of dp[i-K] becomes // zero if (mp[dp[i - K]] == 0) { mp.erase(dp[i - K]); } } // Calculating final answer ans = max(ans, dp[i]); } return ans;}// Driver codeint main(){ int arr[] = { 1, 2, -2, 4, 3, 1 }; int N = sizeof(arr) / sizeof(int); int K = 2; cout << max_sum(arr, N, K); return 0;} |
Java
// Java program to// find the maximum sum// subsequence such that// two adjacent element// have atmost difference// of K in their indicesimport java.util.*;class GFG{ static int max_sum(int[] arr, int N, int K) { // DP Array to store the // maximum sum obtained // till now int[] dp = new int[N]; // Ordered map to store DP // values in a window ok K HashMap<Integer, Integer> mp = new HashMap<>(); // Initializing dp[0]=arr[0] dp[0] = arr[0]; // Inserting value of DP[0] // in map if(mp.containsKey(dp[0])) { mp.put(dp[0], mp.get(dp[0]) + 1); } else{ mp.put(dp[0], 1); } // Initializing final answer // with dp[0] int ans = dp[0]; for (int i = 1; i < N; i++) { // when i<k there is no // need to delete elements // from map as window is // less than K if (i < K) { // Evaluating DP[i] // from recurrence Set<Integer> keySet = mp.keySet(); ArrayList<Integer> Keys = new ArrayList<Integer>(keySet); dp[i] = Math.max(Keys.get(Keys.size()-1) + arr[i], arr[i]); // Inserting dp value in map if(mp.containsKey(dp[i])) { mp.put(dp[i], mp.get(dp[i]) + 1); } else{ mp.put(dp[i], 1); } } else { Set<Integer> keySet = mp.keySet(); ArrayList<Integer> Keys = new ArrayList<Integer>(keySet); dp[i] = Math.max(Keys.get(Keys.size()-1) + arr[i], arr[i]); if(mp.containsKey(dp[i])) { mp.put(dp[i], mp.get(dp[i]) + 1); } else{ mp.put(dp[i], 1); } // Deleting dp[i-k] from // map because window size // has become K+1 if(mp.containsKey(dp[i - K])) { mp.put(dp[i - K], mp.get(dp[i - K]) - 1); } else{ mp.put(dp[i - K], - 1); } // Erase the key from if // count of dp[i-K] becomes // zero if (mp.get(dp[i - K]) == 0) { mp.remove(dp[i - K]); } } // Calculating final answer ans = Math.max(ans, dp[i]); } return ans; } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, -2, 4, 3, 1 }; int N = arr.length; int K = 2; System.out.println(max_sum(arr, N, K)); }}// This code is contributed by divyesh072019 |
Python3
# Python3 program to# find the maximum sum# subsequence such that# two adjacent element# have atmost difference# of K in their indicesdef max_sum(arr, N, K): # DP Array to store the # maximum sum obtained # till now dp = [0 for i in range(N)] # Ordered map to store DP # values in a window ok K mp = dict() # Initializing dp[0]=arr[0] dp[0] = arr[0]; # Inserting value of DP[0] # in map mp[dp[0]] = 1 # Initializing final answer # with dp[0] ans = dp[0]; for i in range(1, N): # when i<k there is no # need to delete elements # from map as window is # less than K if (i < K): # Initializing iterator # to end af map it = list(mp)[-1] # Evaluating DP[i] # from recurrence dp[i] = max(it + arr[i], arr[i]) # Inserting dp value in map if dp[i] in mp: mp[dp[i]] += 1 else: mp[dp[i]] = 1 else: it = list(mp)[-1] dp[i] = max(it + arr[i],arr[i]); if dp[i] in mp: mp[dp[i]] += 1 else: mp[dp[i]] = 1 # Deleting dp[i-k] from # map because window size # has become K+1 if mp[dp[i - K]] == 0: mp[dp[i - K]] -= 1 # Calculating final answer ans = max(ans, dp[i]); return ans;# Driver codeif __name__=='__main__': arr = [ 1, 2, -2, 4, 3, 1 ] N = len(arr) K = 2; print(max_sum(arr, N, K)) # This code is contributed by rutvik_56 |
C#
// C# program to// find the maximum sum// subsequence such that// two adjacent element// have atmost difference// of K in their indicesusing System;using System.Collections.Generic; using System.Linq;class GFG { static int max_sum(int[] arr, int N, int K) { // DP Array to store the // maximum sum obtained // till now int[] dp = new int[N]; // Ordered map to store DP // values in a window ok K Dictionary<int, int> mp = new Dictionary<int, int>(); // Initializing dp[0]=arr[0] dp[0] = arr[0]; // Inserting value of DP[0] // in map if(mp.ContainsKey(dp[0])) { mp[dp[0]]++; } else{ mp[dp[0]] = 1; } // Initializing final answer // with dp[0] int ans = dp[0]; for (int i = 1; i < N; i++) { // when i<k there is no // need to delete elements // from map as window is // less than K if (i < K) { // Evaluating DP[i] // from recurrence dp[i] = Math.Max(mp.Keys.Last() + arr[i], arr[i]); // Inserting dp value in map if(mp.ContainsKey(dp[i])) { mp[dp[i]]++; } else{ mp[dp[i]] = 1; } } else { dp[i] = Math.Max(mp.Keys.Last() + arr[i], arr[i]); if(mp.ContainsKey(dp[i])) { mp[dp[i]]++; } else{ mp[dp[i]] = 1; } // Deleting dp[i-k] from // map because window size // has become K+1 if(mp.ContainsKey(dp[i - K])) { mp[dp[i - K]]--; } else{ mp[dp[i - K]] = -1; } // Erase the key from if // count of dp[i-K] becomes // zero if (mp[dp[i - K]] == 0) { mp.Remove(dp[i - K]); } } // Calculating final answer ans = Math.Max(ans, dp[i] + 1); } return ans; } // Driver code static void Main() { int[] arr = { 1, 2, -2, 4, 3, 1 }; int N = arr.Length; int K = 2; Console.Write(max_sum(arr, N, K)); }}// This code is contributed by divyeshrabadiya07 |
Javascript
// JavaScript program to// find the maximum sum// subsequence such that// two adjacent element// have atmost difference// of K in their indicesfunction max_sum(arr, N, K) { // DP Array to store the // maximum sum obtained // till now let dp = new Array(N).fill(0); // Map to store DP values // in a window of K let mp = new Map(); // Initializing dp[0]=arr[0] dp[0] = arr[0]; // Inserting value of DP[0] // in map mp.set(dp[0], 1); // Initializing final answer // with dp[0] let ans = dp[0]; for (let i = 1; i < N; i++) { // when i<k there is no // need to delete elements // from map as window is // less than K if (i < K) { // Initializing iterator // to end of map let it = Array.from(mp.keys()).pop(); // Evaluating DP[i] // from recurrence dp[i] = Math.max(it + arr[i], arr[i]); // Inserting dp value in map if (mp.has(dp[i])) { mp.set(dp[i], mp.get(dp[i]) + 1); } else { mp.set(dp[i], 1); } } else { it = Array.from(mp.keys()).pop(); dp[i] = Math.max(it + arr[i], arr[i]); if (mp.has(dp[i])) { mp.set(dp[i], mp.get(dp[i]) + 1); } else { mp.set(dp[i], 1); } // Deleting dp[i-k] from // map because window size // has become K+1 if (mp.get(dp[i - K]) === 1) { mp.delete(dp[i - K]); } else { mp.set(dp[i - K], mp.get(dp[i - K]) - 1); } } // Calculating final answer ans = Math.max(ans, dp[i]); } return ans;}// Driver code let arr = [ 1, 2, -2, 4, 3, 1 ] let N = (arr).length let K = 2; console.log(max_sum(arr, N, K)) // This code is contributed by lokeshpotta20. |
Output:
11
Time Complexity: O(N*log(K))
Auxiliary Space: O(N) because it using extra space for array dp and map mp
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!
