สมมติว่าเรามีอาร์เรย์ที่มีองค์ประกอบ n ตัว เราต้องหาอาร์เรย์ย่อยที่อยู่ติดกันของความยาวที่กำหนด k ซึ่งมีค่าเฉลี่ยสูงสุด เราต้องคืนค่าค่าเฉลี่ยสูงสุด
ดังนั้น หากอินพุตเป็น [1,13,-5,-8,48,3] และ k =4 เอาต์พุตจะเป็น 12.0 เนื่องจาก (13-5-8+48)/4 =12.0
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ผลรวม :=0
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
sum :=sum + nums[i]
-
-
maxi :=ผลรวม
-
สำหรับการเริ่มต้น i :=k เมื่อฉัน <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -
-
sum :=sum + nums[i] - nums[i - k]
-
ถ้า sum> maxi แล้ว −
-
maxi :=ผลรวม
-
-
-
กลับ maxi / k
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
double maxi = sum;
for (int i = k; i < nums.size(); i++) {
sum += nums[i] - nums[i - k];
if (sum > maxi) {
maxi = sum;
}
}
return maxi / k;
}
};
main(){
Solution ob;
vector<int> v = {1,13,-5,-8,48,3};
cout << (ob.findMaxAverage(v, 4));
} อินพุต
{1,13,-5,-8,48,3}, 4 ผลลัพธ์
12
