Subarray เฉลี่ยสูงสุด I ใน C ++

สมมติว่าเรามีอาร์เรย์ที่มีองค์ประกอบ 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