ในปัญหานี้ เราได้รับอาร์เรย์ arr[] และตัวเลข k งานของเราคือ ค้นหาผลรวมสูงสุด (หรือต่ำสุด) ของอาร์เรย์ย่อยขนาด k
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: arr[] ={55, 43, 12, 76, 89, 25, 99} , k =2
ผลลัพธ์: 165
คำอธิบาย:
อาร์เรย์ย่อยของขนาด 2 มีผลรวม =76 + 89 =165
แนวทางการแก้ปัญหา
วิธีง่ายๆ ในการแก้ปัญหาคือการค้นหาอาร์เรย์ย่อยขนาด k ทั้งหมด จากนั้นคืนค่าผลรวมด้วยค่าสูงสุด
แนวทางอื่น กำลังใช้ หน้าต่างบานเลื่อน เราจะหาผลรวมของอาร์เรย์ย่อยขนาด k สำหรับสิ่งนี้ อาร์เรย์ย่อยขนาด k ถัดไป เราจะลบองค์ประกอบดัชนีสุดท้ายและเพิ่มองค์ประกอบดัชนีถัดไป
แล้วคืนค่าผลรวมของอาร์เรย์ย่อยด้วยค่าสูงสุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int findMaxSumSubarray(int arr[], int n, int k) {
if (n < k) {
cout << "Invalid";
return -1;
}
int maxSum = 0;
for (int i=0; i<k; i++)
maxSum += arr[i];
int curr_sum = maxSum;
for (int i=k; i<n; i++) {
curr_sum += arr[i] - arr[i-k];
maxSum = max(maxSum, curr_sum);
}
return maxSum;
}
int main() {
int arr[] = {55, 43, 12, 76, 89, 25, 99};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"The sum of subarray with max sum of size "<<k<<" is "<<findMaxSumSubarray(arr, n, k);
return 0;
} ผลลัพธ์
The sum of subarray with max sum of size 2 is 165
