ในปัญหานี้ เราจะได้รับอาร์เรย์ arr[] ขนาด n และตัวเลข k งานของเราคือการสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดที่มีองค์ประกอบที่อยู่ห่างไกลอย่างน้อยที่สุด
คำอธิบายปัญหา − เราจำเป็นต้องหาผลรวมของอาร์เรย์ย่อยเพื่อให้องค์ประกอบของอาร์เรย์ย่อยดึงมาจากอาร์เรย์ที่มีดัชนีอยู่ที่ระยะ k และผลรวมจะถูกขยายให้ใหญ่สุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
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 แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการค้นหาอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมดที่ตรงตามเงื่อนไขที่กำหนด หาผลรวมของอาร์เรย์ทั้งหมดและคืนค่าสูงสุดของทั้งหมด
วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการใช้วิธีการโปรแกรมแบบไดนามิกโดยการสร้างอาร์เรย์เพื่อเก็บผลรวมสูงสุดจนถึงองค์ประกอบปัจจุบัน สำหรับองค์ประกอบปัจจุบัน เราสามารถพิจารณามันสำหรับผลรวมหรือทิ้งมันสำหรับผลรวม แล้วแต่จำนวนใดจะเพิ่มผลรวมจนถึงดัชนีปัจจุบัน
หากเราพิจารณาผลรวม sum[i] =sum[i + k + 1] + arr[i+1] มิฉะนั้น ให้ทิ้งผลรวม sum[i] =sum[i+1]และในตอนท้าย คืนยอดรวมสูงสุดซึ่งอยู่ที่ผลรวม[0].
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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
