Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm tổng lớn nhất có thể cho một dãy con sao cho không có hai phần tử nào xuất hiện ở khoảng cách
Đối với điều này, chúng ta sẽ được cung cấp một mảng chứa N số xen kẽ và một giá trị K. Nhiệm vụ của chúng ta là tìm tổng lớn nhất của dãy con bao gồm các phần tử không gần hơn K. Ví dụ
#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;
} Đầu ra
15
