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 = N-2 to 0. Base Case: MS[N-1] = arr[N-1] 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[n-1] 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 codeint 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;} |
Java
// Java program to find maximum sum subsequence// such that elements are at least k distance// away.import java.io.*;class GFG { static int maxSum(int arr[], int N, int k) { // MS[i] is going to store maximum sum // subsequence in subarray from arr[i] // to arr[n-1] int MS[] = new int[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] = Math.max(arr[i], MS[i + 1]); else MS[i] = Math.max(arr[i] + MS[i + k + 1], MS[i + 1]); } return MS[0]; } // Driver code public static void main(String[] args) { int N = 10, k = 2; int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 }; System.out.println(maxSum(arr, N, k)); }}// This code is contributed by Prerna Saini |
Python3
# Python3 program to find maximum# sum subsequence such that elements# are at least k distance away.def maxSum(arr, N, k): # MS[i] is going to store maximum sum # subsequence in subarray from arr[i] # to arr[n-1] MS = [0 for i in range(N)] # We fill MS from right to left. MS[N - 1] = arr[N - 1] for i in range(N - 2, -1, -1): 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 codeN = 10; k = 2arr = [ 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 ]print(maxSum(arr, N, k)) # This code is contributed by Anant Agarwal. |
C#
// C# program to find maximum sum// subsequence such that elements// are at least k distance away.using System; class GFG { static int maxSum(int []arr, int N, int k) { // MS[i] is going to store maximum sum // subsequence in subarray from arr[i] // to arr[n-1] int []MS = new int[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] = Math.Max(arr[i], MS[i + 1]); else MS[i] = Math.Max(arr[i] + MS[i + k + 1], MS[i + 1]); } return MS[0]; } // Driver code public static void Main() { int N = 10, k = 2; int []arr = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 }; Console.WriteLine(maxSum(arr, N, k)); }}// This code is contributed by Anant Agarwal. |
PHP
<?php// PHP program to find // maximum sum subsequence// such that elements are // at least k distance// away.function maxSum($arr, $N, $k){ // MS[i] is going to // store maximum sum // subsequence in // subarray from arr[i] // to arr[n-1] // We fill MS from // right to left. $MS[$N - 1] = $arr[$N - 1]; for ($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$N = 10; $k = 2;$arr = array(50, 70, 40, 50, 90, 70, 60, 40, 70, 50);echo(maxSum($arr, $N, $k));// This code is contributed by Ajit.?> |
Javascript
<script> function maxSum(arr, N, k) { // MS[i] is going to store maximum sum subsequence // in subarray from arr[i] to arr[n-1] let MS = []; MS.length = N; MS[N-1] = arr[N-1]; for(let i = N - 2; i >= 0; i--){ if(i+k+1 >= N){ MS[i] = Math.max(arr[i], MS[i+1]); } else{ MS[i] = Math.max(arr[i] + MS[i+k+1], MS[i+1]); } } return MS[0]; } let N = 10, k = 2; let arr = [ 50, 70, 40, 50, 90, 70, 60, 40, 70, 50]; document.write(maxSum(arr, N, k)); // This code is contributed by lokeshmvs21.</script> |
Output
230
Time Complexity : O(n) Auxiliary Space : O(n) This article is contributed by Sayan Mahapatra. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
