Maximum sum possible for a sub-sequence such that no two elements appear at a distance < K in the array in C++
-
10-09-2020 - |
Domanda
In this tutorial, we will be discussing a program to find maximum sum possible for a sub-sequence such that no two elements appear at a distance < K in the array.
For this we will be provided with an array containing N intergers and a value K. Our task is to find the maximum sum of the subsequence including elements not nearer than K.
Example
#include <bits/stdc++.h> using namespace std; //returning maximum sum int maxSum(int* arr, int k, int n) { if (n == 0) return 0; if (n == 1) return arr[0]; if (n == 2) return max(arr[0], arr[1]); int dp[n]; dp[0] = arr[0]; for (int i = 1; i <= k; i++) dp[i] = max(arr[i], dp[i - 1]); for (int i = k + 1; i < n; i++) dp[i] = max(arr[i], dp[i - (k + 1)] + arr[i]); int max = *(std::max_element(dp, dp + n)); return max; } int main() { int arr[] = { 6, 7, 1, 3, 8, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; cout << maxSum(arr, k, n); return 0; }
Output
15
Non affiliato a Tutorialspoint