Maximum sum subsequence with atleast k distant elements
Given an array and a number k, find a subsequence such that

 Sum of elements in subsequence is maximum
 Indices of elements of subsequence differ atleast by k
Examples
Input : arr[] = {4, 5, 8, 7, 5, 4, 3, 4, 6, 5} k = 2 Output: 19 Explanation: The highest value is obtained if you pick indices 1, 4, 7, 10 giving 4 + 7 + 3 + 5 = 19 Input: arr[] = {50, 70, 40, 50, 90, 70, 60, 40, 70, 50} k = 2 Output: 230 Explanation: There are 10 elements and k = 2. If you select 2, 5, and 9 you get a total value of 230, which is the maximum possible.
A simple solution is to consider all subsequences one by one. In every subsequence, check for distance condition and return the maximum sum subsequence.
An efficient solution is to use dynamic programming.
There are two cases:



 If we select element at index i such that i + k + 1 >= N, then we cannot select any other element as part of the subsequence. Hence we need to decide whether to select this element or one of the elements after it.
 If we select element at index i such that i + k + 1 < N, then the next element we can select is at i + k + 1 index. Thus we need to decide whether to select these two elements, or move on to the next adjacent element.


These two cases can be written as:
Let MS[i] denotes the maximum sum of subsequence from i to N. Base Case: MS[N1] = arr[N1] If i + 1 + k >= N MS[i] = max(arr[i], MS[i+1]), Else MS[i] = max(arr[i] + MS[i+k+1], MS[i+1]) Evidently, the solution to the problem is to find MS[0].
Below is the implementation:
 C++

// CPP program to find maximum sum subsequence
// such that elements are at least k distance
// away.
#include <bits/stdc++.h>
using
namespace
std;
int
maxSum(
int
arr[],
int
N,
int
k)
{
// MS[i] is going to store maximum sum
// subsequence in subarray from arr[i]
// to arr[n1]
int
MS[N];
// We fill MS from right to left.
MS[N  1] = arr[N  1];
for
(
int
i = N  2; i >= 0; i) {
if
(i + k + 1 >= N)
MS[i] = max(arr[i], MS[i + 1]);
else
MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
}
return
MS[0];
}
// Driver code
int
main()
{
int
N = 10, k = 2;
int
arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
cout << maxSum(arr, N, k);
return
0;
}


 Output:

230
Time Complexity : O(n)
Auxiliary Space : O(n)
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide