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 9

Input: 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:

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.

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 9

Input: 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:

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.