Maximum sum Subsequence with index difference K
Given an array of integers arr[] and an integer k, we need to find the maximum sum of a subsequence such that the index difference between any two elements of the subsequence is k.
Examples:
Input: arr = [1, 2, 3, 4, 5], k = 2
Output: 9
Explanation: The maximum sum subsequence with index difference 2 is [1, 3, 5] with sum 9Input: arr = [4, 1, 3, 5, 6, 9, 7, 8] and k = 3
Output: 16
Explanation: The maximum sum subsequence with index difference 3 is [4, 5, 7] with sum 16
Approach: The approach is to use a dynamic programming method.
Initialize an array dp of size n (where n is the length of arr) with all elements initialized to 0. Then, for a subsequence of length 1 (i.e., i < k), dp[i] is initialized to arr[i]. This is because a subsequence of length 1 is the maximum sum subsequence for indices i < k. Now, for a subsequence of length greater than 1 (i.e., i ≥ k), dp[i] is computed by adding the current element arr[i] to the maximum sum subsequence ending at index i-k. The maximum sum subsequence can be obtained by taking the maximum value in the dp array.
Below are the steps for the above approach:
- Initialize a variable n to store the length of the given array arr[].
- Initialize an array dp of the same length with all elements initialized to 0. This dp array will store the maximum sum of a subsequence that ends at index i.
- Initialize dp for a subsequence of length 1. For each index, i from 0 to k-1, set dp[i] to arr[i] since a subsequence of length 1 is the maximum sum subsequence for these indices.
- Compute dp for a subsequence of length greater than 1. For each index, i from k to n-1 (where n is the length of arr), set dp[i] to the sum of the element at index i and the maximum sum subsequence ending at index i-k, dp[i] = dp[i-k] + arr[i].
- Return the maximum value in the dp array as the maximum sum subsequence.
Below is the code for the above approach:
C++
// CPP code for above approach #include <bits/stdc++.h> using namespace std; int max_sum_subsequence(vector< int > arr, int k) { int n = arr.size(); vector< int > dp(n, 0); // Initialize dp for subsequence of length 1 for ( int i = 0; i < k; i++) { dp[i] = arr[i]; } // Compute dp for subsequence of length > 1 for ( int i = k; i < n; i++) { dp[i] = dp[i - k] + arr[i]; } // Return maximum sum subsequence return *max_element(dp.begin(), dp.end()); } int main() { vector< int > arr1 = { 1, 2, 3, 4, 5 }; int k = 2; cout << max_sum_subsequence(arr1, k) << endl; return 0; } // This code is contributed by Susobhan Akhuli |
Java
// Java code for above approach import java.util.*; public class Main { public static int max_sum_subsequence(List<Integer> arr, int k) { int n = arr.size(); List<Integer> dp = new ArrayList<>(Collections.nCopies(n, 0 )); // Initialize dp for subsequence of length 1 for ( int i = 0 ; i < k; i++) { dp.set(i, arr.get(i)); } // Compute dp for subsequence of length > 1 for ( int i = k; i < n; i++) { dp.set(i, dp.get(i - k) + arr.get(i)); } // Return maximum sum subsequence return Collections.max(dp); } public static void main(String[] args) { List<Integer> arr1 = Arrays.asList( 1 , 2 , 3 , 4 , 5 ); int k = 2 ; System.out.println(max_sum_subsequence(arr1, k)); } } // This code is contributed by Susobhan Akhuli |
Python3
# Python code for above approach def max_sum_subsequence(arr, k): n = len (arr) dp = [ 0 ] * n # Initialize dp for subsequence of length 1 for i in range (k): dp[i] = arr[i] # Compute dp for subsequence of length > 1 for i in range (k, n): dp[i] = dp[i - k] + arr[i] # Return maximum sum subsequence return max (dp) arr1 = [ 1 , 2 , 3 , 4 , 5 ] k = 2 print (max_sum_subsequence(arr1, k)) |
C#
// C# code for above approach using System; using System.Collections.Generic; using System.Linq; class GFG { static int MaxSumSubsequence(List< int > arr, int k) { int n = arr.Count; List< int > dp = new List< int >(n); // Initialize dp for subsequence of length 1 for ( int i = 0; i < k; i++) { dp.Add(arr[i]); } // Compute dp for subsequence of length > 1 for ( int i = k; i < n; i++) { dp.Add(dp[i - k] + arr[i]); } // Return maximum sum subsequence return dp.Max(); } static void Main() { List< int > arr = new List< int >{ 1, 2, 3, 4, 5 }; int k = 2; Console.WriteLine(MaxSumSubsequence(arr, k)); } } // This code is contributed by Susobhan Akhuli |
Javascript
// Javascript code for above approach function maxSumSubsequence(arr, k) { let n = arr.length; let dp = new Array(n).fill(0); // Initialize dp for subsequence of length 1 for (let i = 0; i < k; i++) { dp[i] = arr[i]; } // Compute dp for subsequence of length > 1 for (let i = k; i < n; i++) { dp[i] = dp[i - k] + arr[i]; } // Return maximum sum subsequence return Math.max(...dp); } let arr1 = [1, 2, 3, 4, 5]; let k = 2; console.log(maxSumSubsequence(arr1, k)); // This code is contributed by Susobhan Akhuli |
9
Time Complexity: O(N), where N is the number of elements of the array.
Auxiliary Space: O(N), as we use a DP array of size N.