Trong bài toán này, chúng ta cho một mảng arr [] có kích thước n và một số k. Ourtask là tạo một chương trình để tìm tổng phụ tối đa với các phần tử ở xa atleastk.
Mô tả sự cố - Chúng ta cần tìm tổng các mảng con sao cho các phần tử của mảng con được lấy từ mảng có chỉ số của nó ở khoảng cách k và tổng là cực đại.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {2, 3, 7, 9, 2, 8, 3} Đầu ra
15
Giải thích
All subsequences that satisfy the given condition,
{2, 9, 3}, Sum = 14
{3, 2}, Sum = 5
{7, 8}, Sum = 15 Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm tất cả các mảng con có thể thỏa mãn điều kiện đã cho. Tìm tổng của tất cả các mảng và trả về giá trị tối đa của tất cả.
Một giải pháp hiệu quả hơn cho vấn đề này là sử dụng phương pháp lập trình động bằng cách tạo một mảng để lưu trữ tổng lớn nhất cho đến phần tử hiện tại. Đối với phần tử hiện tại, chúng ta có thể xem xét nó cho tổng hoặc loại bỏ nó cho tổng, lấy phần tử nào làm tăng tổng cho đến chỉ số hiện tại.
Nếu chúng ta xem xét nó cho tổng, sum [i] =sum [i + k + 1] + arr [i + 1] Nếu không thì loại bỏ nó cho tổng, sum [i] =sum [i + 1] Và ở cuối trả về tổng lớn nhất bằng tổng [0].
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum sum subsequence with at-least k distant elements is 230