ข้อความโจทย์
กำหนดอาร์เรย์และตัวเลขสองจำนวน M และ K เราต้องการหาผลรวมของซับอาร์เรย์ขนาด K จำนวน M อันดับแรก (ไม่ทับซ้อนกัน) ในอาร์เรย์ (ลำดับของอาร์เรย์คงที่) K คือขนาดของซับอาร์เรย์ และ M คือจำนวนซับอาร์เรย์ สมมติว่าขนาดอาร์เรย์มากกว่า m*k หากขนาดอาร์เรย์ทั้งหมดไม่ใช่จำนวนคูณของ k เราสามารถใช้ซับอาร์เรย์สุดท้ายแบบไม่เต็มได้
ตัวอย่าง
ถ้าอาร์เรย์ที่กำหนดคือ = {2, 10, 7, 18, 5, 33, 0} N = 7, M = 3 และ K = 1 ผลลัพธ์จะเป็น 61 โดยซับเซตคือ:
{33, 18, 10}
อัลกอริทึม
- สร้างอาร์เรย์ presum ซึ่งแต่ละดัชนีเก็บผลรวมขององค์ประกอบทั้งหมดจาก 'index' ถึง 'index + K' ในอาร์เรย์ที่กำหนด ขนาดของอาร์เรย์ผลรวมจะเป็น n+1-k
- หากเรารวมซับอาร์เรย์ขนาด k เราจะไม่สามารถรวมองค์ประกอบใดๆ ของซับอาร์เรย์นั้นอีกในซับอาร์เรย์อื่นๆ ได้ เนื่องจากจะสร้างซับอาร์เรย์ที่ทับซ้อนกัน ดังนั้นเราจึงทำการเรียกฟังก์ชันแบบเวียนเกิดโดยตัดออก k องค์ประกอบของซับอาร์เรย์ที่รวมไว้
- หากเราตัดซับอาร์เรย์ออก เราสามารถใช้องค์ประกอบ k-1 ตัวถัดไปของซับอาร์เรย์นั้นในซับอาร์เรย์อื่นๆ ได้ ดังนั้นเราจะเรียกฟังก์ชันเวียนเกิดโดยตัดเฉพาะองค์ประกอบแรกของซับอาร์เรย์นั้น
- สุดท้ายคืนค่า max(included sum, excluded sum)
ตัวอย่างโค้ด C++
#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
