- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

In this problem, we are given an array arr[] of size n and a number k. Our task is to create a program to find the maximum sum subsequence with atleast k distant elements.

**Problem Description** − We need to find the sum of subarrays such that the elements of the subarray are taken from the array whose index is at k distance and the sum is maximized.

**Let’s take an example to understand the problem,**

arr[] = {2, 3, 7, 9, 2, 8, 3}

15

All subsequences that satisfy the given condition, {2, 9, 3}, Sum = 14 {3, 2}, Sum = 5 {7, 8}, Sum = 15

A simple solution to the problem is by finding all possible subarrays that satisfy the given condition. Find the sum of all arrays and return the maximum of all.

A more efficient solution to the problem is by using a dynamic programming approach by creating an array to store the maximum sum until the current element. For the current element, we can either consider it for the sum or discard it for the sum, taking whichever increases the sum till the current index.

If we consider it for the sum, sum[i] = sum[i + k + 1] + arr[i+1] Otherwise discard it for the sum, sum[i] = sum[i+1] And at the end return the maximum sum which is at the sum[0].

**Program to illustrate the working of our solution,**

#include <bits/stdc++.h> using namespace std; int calcMaxSubSeqSum(int arr[], int N, int k){ int maxSumDP[N]; maxSumDP[N − 1] = arr[N − 1]; for (int i = N − 2; i >= 0; i−−) { if (i + k + 1 >= N) maxSumDP[i] = max(arr[i], maxSumDP[i + 1]); else maxSumDP[i] = max(arr[i] + maxSumDP[i + k + 1], maxSumDP[i + 1]); } return maxSumDP[0]; } int main() { int N = 10, k = 2; int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 }; cout<<"The maximum sum subsequence with at−least k distant elements is "<<calcMaxSubSeqSum(arr, N, k); return 0; }

The maximum sum subsequence with at-least k distant elements is 230

- Related Questions & Answers
- Maximum sum subsequence with at-least k distant elements in C++
- Shortest Subarray with Sum at Least K in C++
- Largest sum subarray with at-least k numbers in C++
- Maximum value K such that array has at-least K elements that are >= K in C++
- Subarray sum with at least two elements in JavaScript
- Python program to find Non-K distant elements
- Program to find k where k elements have value at least k in Python
- Maximum sum alternating subsequence in C++ program
- Program to find length of longest increasing subsequence with at least k odd values in Python
- Program to find minimum sum subsequence by taking at least one element from consecutive 3 elements in python
- Longest Substring with At Least K Repeating Characters in C++
- Maximum sum alternating subsequence in C++
- Maximum Sum Decreasing Subsequence in C++
- Maximum subarray sum by flipping signs of at most K array elements in C++
- Maximum Sum Increasing Subsequence using DP in C++ program

Advertisements