Maximum subsequence sum such that all elements are K distance apart
Given an array arr[] of N integers and another integer K. The task is to find the maximum sum of a subsequence such that the difference of the indices of all consecutive elements in the subsequence in the original array is exactly K. For example, if arr[i] is the first element of the subsequence then the next element has to be arr[i + k] then arr[i + 2k] and so on.
Examples:
Input: arr[] = {2, -3, -1, -1, 2}, K = 2
Output: 3
Input: arr[] = {2, 3, -1, -1, 2}, K = 3
Output: 5
Approach: There are K sequences possible where the elements are K distance apart and these can be of the forms:
0, 0 + k, 0 + 2k, …, 0 + n*k
1, 1 + k, 1 + 2k, …, 1 + n*k
2, 2 + k, 2 + 2k, …, 2 + n*k
k-1, k-1 + k, k-1 + 2k, …, k-1 + n*k
Now, any subarray of the sequences is a subsequence of the original array where elements are K distance apart from each other.
So, the task now reduces to find the maximum subarray sum of these sequences which can be found by Kadane’s algorithm.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum subarray sum // for the array {a[i], a[i + k], a[i + 2k], ...} int maxSubArraySum( int a[], int n, int k, int i) { int max_so_far = INT_MIN, max_ending_here = 0; while (i < n) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; i += k; } return max_so_far; } // Function to return the sum of // the maximum required subsequence int find( int arr[], int n, int k) { // To store the result int maxSum = 0; // Run a loop from 0 to k for ( int i = 0; i <= min(n, k); i++) { int sum = 0; // Find the maximum subarray sum for the // array {a[i], a[i + k], a[i + 2k], ...} maxSum = max(maxSum, maxSubArraySum(arr, n, k, i)); } // Return the maximum value return maxSum; } // Driver code int main() { int arr[] = { 2, -3, -1, -1, 2 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 2; cout << find(arr, n, k); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the maximum subarray sum // for the array {a[i], a[i + k], a[i + 2k], ...} static int maxSubArraySum( int a[], int n, int k, int i) { int max_so_far = Integer.MIN_VALUE, max_ending_here = 0 ; while (i < n) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0 ) max_ending_here = 0 ; i += k; } return max_so_far; } // Function to return the sum of // the maximum required subsequence static int find( int arr[], int n, int k) { // To store the result int maxSum = 0 ; // Run a loop from 0 to k for ( int i = 0 ; i <= Math.min(n, k); i++) { int sum = 0 ; // Find the maximum subarray sum for the // array {a[i], a[i + k], a[i + 2k], ...} maxSum = Math.max(maxSum, maxSubArraySum(arr, n, k, i)); } // Return the maximum value return maxSum; } // Driver code public static void main(String[] args) { int arr[] = { 2 , - 3 , - 1 , - 1 , 2 }; int n = arr.length; int k = 2 ; System.out.println(find(arr, n, k)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to return the maximum subarray sum # for the array {a[i], a[i + k], a[i + 2k], ...} import sys def maxSubArraySum(a, n, k, i): max_so_far = - sys.maxsize; max_ending_here = 0 ; while (i < n): max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here): max_so_far = max_ending_here; if (max_ending_here < 0 ): max_ending_here = 0 ; i + = k; return max_so_far; # Function to return the sum of # the maximum required subsequence def find(arr, n, k): # To store the result maxSum = 0 ; # Run a loop from 0 to k for i in range ( 0 , min (n, k) + 1 ): sum = 0 ; # Find the maximum subarray sum for the # array {a[i], a[i + k], a[i + 2k], ...} maxSum = max (maxSum, maxSubArraySum(arr, n, k, i)); # Return the maximum value return maxSum; # Driver code if __name__ = = '__main__' : arr = [ 2 , - 3 , - 1 , - 1 , 2 ]; n = len (arr); k = 2 ; print (find(arr, n, k)); # This code is contributed by Princi Singh |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum subarray sum // for the array {a[i], a[i + k], a[i + 2k], ...} static int maxSubArraySum( int []a, int n, int k, int i) { int max_so_far = int .MinValue, max_ending_here = 0; while (i < n) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; i += k; } return max_so_far; } // Function to return the sum of // the maximum required subsequence static int find( int []arr, int n, int k) { // To store the result int maxSum = 0; // Run a loop from 0 to k for ( int i = 0; i <= Math.Min(n, k); i++) { // Find the maximum subarray sum for the // array {a[i], a[i + k], a[i + 2k], ...} maxSum = Math.Max(maxSum, maxSubArraySum(arr, n, k, i)); } // Return the maximum value return maxSum; } // Driver code public static void Main() { int []arr = {2, -3, -1, -1, 2}; int n = arr.Length; int k = 2; Console.WriteLine(find(arr, n, k)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximum subarray sum // for the array {a[i], a[i + k], a[i + 2k], ...} function maxSubArraySum(a, n, k, i) { let max_so_far = Number.MIN_VALUE, max_ending_here = 0; while (i < n) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; i += k; } return max_so_far; } // Function to return the sum of // the maximum required subsequence function find(arr, n, k) { // To store the result let maxSum = 0; // Run a loop from 0 to k for (let i = 0; i <= Math.min(n, k); i++) { let sum = 0; // Find the maximum subarray sum for the // array {a[i], a[i + k], a[i + 2k], ...} maxSum = Math.max(maxSum, maxSubArraySum(arr, n, k, i)); } // Return the maximum value return maxSum; } // Driver code let arr = [ 2, -3, -1, -1, 2 ]; let n = arr.length; let k = 2; document.write(find(arr, n, k)); </script> |
3
Time Complexity: O(min(n,k)*n)
Auxiliary Space: O(1)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Approach(Using dynamic programming):
- Initialize an array dp of size N, where dp[i] represents the maximum sum of a subsequence ending at the ith index.
- Initialize the dp array with the values of the original array.
- Iterate over the array from the Kth index to the end and for each index i, calculate dp[i] as the maximum value of dp[j] + arr[i], where j is the index that is K positions behind i.
- Return the maximum value in the dp array.
Here is the implementation of the above approach:
C++
#include <iostream> #include <vector> #include <algorithm> int maxSubsequenceSum(std::vector< int >& arr, int K) { int N = arr.size(); std::vector< int > dp = arr; for ( int i = K; i < N; ++i) { for ( int j = i - K; j >= i - K; j -= K) { // Corrected loop condition here if (j >= 0) { dp[i] = std::max(dp[i], dp[j] + arr[i]); } } } return *std::max_element(dp.begin(), dp.end()); } int main() { std::vector< int > arr = {2, -3, -1, -1, 2}; int K = 2; std::cout << maxSubsequenceSum(arr, K) << std::endl; // Output: 3 return 0; } |
Java
import java.util.Arrays; public class Main { // Function to find the maximum subsequence sum with a // constraint public static int maxSubsequenceSum( int [] arr, int K) { int N = arr.length; int [] dp = Arrays.copyOf( arr, N); // Initialize a dynamic programming array // Iterate through the elements for ( int i = K; i < N; ++i) { // Find the maximum sum considering the // constraint for ( int j = i - K; j >= i - K && j >= 0 ; j -= K) { dp[i] = Math.max(dp[i], dp[j] + arr[i]); } } // Find and return the maximum value in the dynamic // programming array int max = Arrays.stream(dp).max().getAsInt(); return max; } public static void main(String[] args) { int [] arr = { 2 , - 3 , - 1 , - 1 , 2 }; int K = 2 ; System.out.println( maxSubsequenceSum(arr, K)); // Output: 3 } } |
Python3
def maxSubsequenceSum(arr, K): N = len (arr) dp = arr.copy() for i in range (K, N): for j in range (i - K, i - 2 * K, - K): if j > = 0 : dp[i] = max (dp[i], dp[j] + arr[i]) return max (dp) # Example usage arr = [ 2 , - 3 , - 1 , - 1 , 2 ] K = 2 print (maxSubsequenceSum(arr, K)) # Output: 3 |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to find the maximum subsequence sum with a // limit K static int MaxSubsequenceSum(List< int > arr, int K) { int N = arr.Count; List< int > dp = arr.ToList(); // Create a copy of the // input list for ( int i = K; i < N; ++i) { for ( int j = i - K; j <= i - 1; j++) // Loop corrected here { if (j >= 0) { dp[i] = Math.Max(dp[i], dp[j] + arr[i]); } } } return dp.Max(); } static void Main( string [] args) { List< int > arr = new List< int >{ 2, -3, -1, -1, 2 }; int K = 2; Console.WriteLine( MaxSubsequenceSum(arr, K)); // Output: 3 } } |
Javascript
function maxSubsequenceSum(arr, K) { const N = arr.length; const dp = [...arr]; // Create a copy of the input array for (let i = K; i < N; ++i) { for (let j = i - K; j <= i - 1; j += K) { // Corrected loop condition here if (j >= 0) { dp[i] = Math.max(dp[i], dp[j] + arr[i]); } } } return Math.max(...dp); } const arr = [2, -3, -1, -1, 2]; const K = 2; console.log(maxSubsequenceSum(arr, K)); // Output: 3 |
3
Time Complexity: O(NK), where N is the length of the input array arr and K is the value passed as an argument to the function. This is because there are two nested loops, and the inner loop runs K times for each element in the array, so the overall time complexity is O(NK).
Auxiliary Space: O(N), since the size of the dp array is the same as the size of the input array arr. Therefore, the space complexity is linear in the size of the input.