Maximum subsequence sum such that all elements are K distance apart | C ++ implementation of the approach ; Function to return the maximum subarray sum for the array { a [ i ] , a [ i + k ] , a [ i + 2 k ] , ... } ; Function to return the sum of the maximum required subsequence ; To store the result ; Run a loop from 0 to k ; Find the maximum subarray sum for the array { a [ i ] , a [ i + k ] , a [ i + 2 k ] , ... } ; Return the maximum value ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ; } int find ( int arr [ ] , int n , int k ) { int maxSum = 0 ; for ( int i = 0 ; i <= min ( n , k ) ; i ++ ) { int sum = 0 ; maxSum = max ( maxSum , maxSubArraySum ( arr , n , k , i ) ) ; } return maxSum ; } 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 ; }