Given an array arr[] consisting of integers of length N and an integer K (1 ? k ? N), the task is to find the maximum subsequence sum in the array such that adjacent elements in that subsequence have at least a difference of K in their indices in the original array.
Examples:
Input: arr[] = {1, 2, -2, 4, 3, 1}, K = 4
Output: 4
Explanation:
Such Subsequences that can be selected: {1, 3}, {1, 1}, {2, 1}
Subsequence with maximum sum = (1 + 3) = 4
Selected elements are a[0] and a[4] (difference between indices = 4)Input: arr[] = {1, 2, 72, 4, 3}, K = 2
Output: 76
Explanation:
Such Subsequences that can be selected – {{1, 72, 3}, {2, 4}, {2, 3}, {1, 4}, {1, 3}}
Subsequence with maximum sum = (1 + 72 + 3) = 76
Selected elements are a[0], a[2] and a[4] (difference between each indices = 2)
Naive approach: Generate all possible subsets of the array and check for each of the subsets that it satisfies the condition such that two adjacent elements have at least a 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. In which for each element in array consider such that if we take this element then is it contributes into the final sum obtained If yes then add it into the DP array for that element.
Let’s decide the states of ‘dp’. Let dp[i] be the largest possible sum for the sub-array starting from index ‘0’ and ending at index ‘i’. Now, we have to find a recurrence relation between this state and a lower-order state.
Now the Recurrence Relation for the array will have two choices for every index i.
- Choose the current index:
In this case, the element that can be chosen is at index i-k.
So,
dp[i] = arr[i] + dp[i - k]
- Skip the current Index.
In this case, the element that can be chosen is at index i-1.
So,
dp[i] = dp[i - 1]
For every index choose that condition that gives the maximum sum at that index, So the final recurrence relation will be:
dp[i] = max(dp[i – 1], arr[i] + dp[i – k])
Below is the implementation of the above approach.
C++
// C++ implementation to find the// maximum sum subsequence such that// two adjacent element have atleast// difference of K in their indices#include <bits/stdc++.h>using namespace std;// Function to find the maximum// between two elements a and bint maxi(int a, int b){ if (a > b) { return a; } else { return b; }}// Function to find the maximum sum// subsequence such that two adjacent// element have atleast difference// of K in their indicesint max_sum(int arr[], int n, int k){ // DP Array to store the maximum // sum obtained till now int dp[n]; // Either select the first element // or Nothing dp[0] = maxi(0, arr[0]); int i = 1; // Either Select the (i - 1) element // or let the previous best answer be // the current best answer while (i < k) { dp[i] = maxi(dp[i - 1], arr[i]); i++; } i = k; // Either select the best sum // till previous_index or select the // current element + best_sum till index-k while (i < n) { dp[i] = maxi(dp[i - 1], arr[i] + dp[i - k]); i++; } return dp[n - 1];}// Driver Codeint main(){ int arr[] = { 1, 2, -2, 4, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 4; cout << max_sum(arr, n, k); return 0;} |
Java
// Java implementation to find the // maximum sum subsequence such that // two adjacent element have atleast // difference of K in their indices class GFG { // Function to find the maximum sum // subsequence such that two adjacent // element have atleast difference // of K in their indices 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]; // Either select the first element // or Nothing dp[0] = Math.max(0, arr[0]); int i = 1; // Either Select the (i - 1) element // or let the previous best answer be // the current best answer while (i < k) { dp[i] = Math.max(dp[i - 1], arr[i]); i++; } i = k; // Either select the best sum // till previous_index or select the // current element + best_sum till index-k while (i < n) { dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - k]); i++; } return dp[n - 1]; } // Driver Code public static void main (String[] args) { int arr[] = { 1, 2, -2, 4, 3, 1 }; int n = arr.length; int k = 4; System.out.println(max_sum(arr, n, k)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation to find the # maximum sum subsequence such that # two adjacent element have atleast # difference of K in their indices# Function to find the maximum sum # subsequence such that two adjacent # element have atleast difference # of K in their indices def max_sum(arr, n, k) : # DP Array to store the maximum # sum obtained till now dp = [0] * n; # Either select the first element # or Nothing dp[0] = max(0, arr[0]); i = 1; # Either Select the (i - 1) element # or let the previous best answer be # the current best answer while (i < k) : dp[i] = max(dp[i - 1], arr[i]); i += 1; i = k; # Either select the best sum # till previous_index or select the # current element + best_sum till index-k while (i < n) : dp[i] = max(dp[i - 1], arr[i] + dp[i - k]); i += 1; return dp[n - 1]; # Driver Code if __name__ == "__main__" : arr = [ 1, 2, -2, 4, 3, 1 ]; n = len(arr) k = 4; print(max_sum(arr, n, k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation to find the // maximum sum subsequence such that // two adjacent element have atleast // difference of K in their indices using System;class GFG { // Function to find the maximum sum // subsequence such that two adjacent // element have atleast difference // of K in their indices 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]; // Either select the first element // or Nothing dp[0] = Math.Max(0, arr[0]); int i = 1; // Either Select the (i - 1) element // or let the previous best answer be // the current best answer while (i < k) { dp[i] = Math.Max(dp[i - 1], arr[i]); i++; } i = k; // Either select the best sum // till previous_index or select the // current element + best_sum till index-k while (i < n) { dp[i] = Math.Max(dp[i - 1], arr[i] + dp[i - k]); i++; } return dp[n - 1]; } // Driver Code public static void Main() { int []arr = { 1, 2, -2, 4, 3, 1 }; int n = arr.Length; int k = 4; Console.WriteLine(max_sum(arr, n, k)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// javascript implementation to find the // maximum sum subsequence such that // two adjacent element have atleast // difference of K in their indices // Function to find the maximum sum // subsequence such that two adjacent // element have atleast difference // of K in their indices function max_sum(arr , n , k) { // DP Array to store the maximum // sum obtained till now var dp = Array.from({length: n}, (_, i) => 0); // Either select the first element // or Nothing dp[0] = Math.max(0, arr[0]); var i = 1; // Either Select the (i - 1) element // or let the previous best answer be // the current best answer while (i < k) { dp[i] = Math.max(dp[i - 1], arr[i]); i++; } i = k; // Either select the best sum // till previous_index or select the // current element + best_sum till index-k while (i < n) { dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - k]); i++; } return dp[n - 1]; } // Driver Code var arr = [ 1, 2, -2, 4, 3, 1 ]; var n = arr.length; var k = 4; document.write(max_sum(arr, n, k)); // This code is contributed by 29AjayKumar </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
