Mô phỏng thuật toán Trung bình lớn nhất cửa sổ K

Max Average Subarray (size K) · Nhóm: Cửa sổ trượt

Tìm cửa sổ con CỐ ĐỊNH cỡ K có trung bình lớn nhất, bằng cách trượt cửa sổ và cập nhật tổng trong O(1).

Ý tưởng

Tính tổng cửa sổ đầu a[0..K−1], tạm coi là tổng lớn nhất; ghi nhớ vị trí bắt đầu.

Trượt cửa sổ sang phải: newSum = sum − a[trái rời] + a[phải vào]; cập nhật tổng lớn nhất, trung bình lớn nhất = tổng lớn nhất chia K.

Vì sao đúng

Nhờ công thức cộng vào bớt ra, mỗi bước trượt chỉ tốn O(1) thay vì cộng lại K phần tử; tổng cả quá trình là O(n), tránh O(n·K) của cách tính lại mỗi cửa sổ.

Mã Python

def max_average(a, K):
    s = sum(a[:K])              # sum of first window
    best = s                    # best window sum so far
    best_l = 0
    for r in range(K, len(a)):
        l = r - K               # element leaving the window
        s = s - a[l] + a[r]     # slide in O(1)
        if s > best:
            best = s; best_l = r - K + 1
    return best / K             # max average

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.