ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n ซึ่งประกอบด้วยค่าบวกและค่าลบ และจำนวนเต็ม k งานของเราคือ ค้นหาอาร์เรย์ย่อยเฉลี่ยสูงสุดของความยาว k
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: arr[] ={4, -1, 5, 6, -2, 4} k =3
ผลลัพธ์: 10
คำอธิบาย:
อาร์เรย์ย่อยของขนาด 3 ที่มีผลรวมสูงสุดคือ -1, 5, 6 =10
แนวทางการแก้ปัญหา
การแก้ปัญหาทำได้โดยใช้อาร์เรย์เสริม เพื่อเก็บผลรวมสะสมจนถึงดัชนีปัจจุบันในอาร์เรย์
ในการหาผลรวมของอาร์เรย์ย่อย เราจำเป็นต้องคำนวณความแตกต่างระหว่างดัชนีของตำแหน่งของอาร์เรย์ย่อย
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int findMaxSubArrayAverage(int arr[], int n, int k) {
if (k > n)
return -1;
int *auxSumArray = new int[n];
auxSumArray[0] = arr[0];
for (int i=1; i<n; i++)
auxSumArray[i] = auxSumArray[i-1] + arr[i];
int maxSum = auxSumArray[k-1], subEndIndex = k-1;
for (int i=k; i<n; i++) {
int sumVal = auxSumArray[i] - auxSumArray[i-k];
if (sumVal > maxSum) {
maxSum = sumVal;
subEndIndex = i;
}
}
return subEndIndex - k + 1;
}
int main() {
int arr[] = {4, -1, 5, 6, -2, 4};
int k = 3;
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum average subarray of length "<<k<<" begins at index "<<findMaxSubArrayAverage(arr, n, k);
return 0;
} ผลลัพธ์
The maximum average subarray of length 3 begins at index 1
