คำชี้แจงปัญหา
ระบุอาร์เรย์และตัวเลขสองตัว M และ K เราจำเป็นต้องค้นหาผลรวมของอาร์เรย์ย่อย M สูงสุดของขนาด K (ไม่ทับซ้อนกัน) ในอาร์เรย์ (ลำดับของอาร์เรย์ยังคงไม่เปลี่ยนแปลง) K คือขนาดของอาร์เรย์ย่อยและ M คือจำนวนอาร์เรย์ย่อย อาจสันนิษฐานได้ว่าขนาดของอาร์เรย์มากกว่า m*k หากขนาดอาร์เรย์ทั้งหมดไม่ใช่จำนวนคูณของ k เราก็สามารถนำอาร์เรย์สุดท้ายบางส่วนมาใช้ได้
ตัวอย่าง
ถ้าอาร์เรย์ที่ระบุคือ ={2, 10, 7, 18, 5, 33, 0} N =7, M =3 และ K =1 ดังนั้นเอาต์พุตจะเป็น 61 เนื่องจากเซตย่อยคือ −
{33, 18, 10} อัลกอริทึม
- เราสร้าง presum array ซึ่งประกอบด้วยผลรวมดัชนีแต่ละรายการขององค์ประกอบทั้งหมดตั้งแต่ 'index' ถึง 'index + K' ในอาร์เรย์ที่กำหนด และขนาดของอาร์เรย์ผลรวมจะเป็น n+1-k
- ตอนนี้ ถ้าเรารวม subarray ขนาด k แล้ว เราไม่สามารถรวมองค์ประกอบใดๆ ของ subarray นั้นอีกใน subarray อื่น ๆ เนื่องจากจะสร้าง subarray ที่ทับซ้อนกัน ดังนั้นเราจึงทำการเรียกซ้ำโดยไม่รวมองค์ประกอบ k ของอาร์เรย์ย่อยที่รวมอยู่
- หากเราแยกอาร์เรย์ย่อยออกไป เราก็สามารถใช้องค์ประกอบ k-1 ถัดไปของอาร์เรย์ย่อยนั้นในอาร์เรย์ย่อยอื่นๆ ได้ ดังนั้นเราจะทำการเรียกซ้ำโดยไม่รวมองค์ประกอบแรกของอาร์เรย์ย่อยนั้น
- สุดท้ายจะส่งคืน max(included sum, excluded sum)
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void calculatePresumArray(int presum[], int arr[], int n, int k) {
for (int i = 0; i < k; i++) {
presum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++) {
presum[i] += presum[i-1] + arr[i+k-1] - arr[i- 1];
}
}
int maxSumMnonOverlappingSubarray(int presum[], int m, int size, int k, int start) {
if (m == 0)
return 0;
if (start > size - 1)
return 0;
int mx = 0;
int includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum, m - 1, size, k, start + k);
int excludeMax = maxSumMnonOverlappingSubarray(presum, m, size, k, start + 1);
return max(includeMax, excludeMax);
}
int main() {
int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 3, k = 1;
int presum[n + 1 - k] = { 0 };
calculatePresumArray(presum, arr, n, k);
cout << "Maximum sum = " << maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0) << endl;
return 0;
} เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Maximum sum = 61
