Tổng Lớn Nhất Mảng Con Kích Thước KMaximum Subarray of Size K
Hiểu bài
Cho bạn một mảng số nguyên nums và số nguyên k. Tìm tổng lớn nhất của mảng con liên tiếp có đúng k phần tử.
Ví dụ:
nums = [2, 1, 5, 1, 3, 2], k = 3
output = 9 // mảng con [5, 1, 3] có tổng 5+1+3 = 9
nums = [2, 3, 4, 1, 5], k = 2
output = 7 // mảng con [3, 4] có tổng 3+4 = 7Đây là bài nhập môn cho kỹ thuật Cửa sổ trượt (Sliding Window) — cửa sổ kích thước cố định di chuyển từ trái sang phải.
Xem cách cơ bản (chậm hơn)
O(n·k) time, O(1) spacefunction maxSubarrayOfSizeK(nums: number[], k: number): number {
let maxSum = -Infinity
for (let i = 0; i <= nums.length - k; i++) {
let windowSum = 0
for (let j = i; j < i + k; j++) {
windowSum += nums[j]
}
maxSum = Math.max(maxSum, windowSum)
}
return maxSum
}Với mỗi vị trí bắt đầu, ta cộng lại k phần tử từ đầu.
- Khi k lớn (gần n) thì gần O(n²).
- Cửa sổ trượt loại bỏ sự tính toán thừa này.
Lời giải tối ưu
O(n) time, O(1) spacefunction maxSubarrayOfSizeK(nums: number[], k: number): number {
let windowSum = 0
let maxSum = -Infinity
let left = 0
for (let right = 0; right < nums.length; right++) {
windowSum += nums[right] // mở rộng cửa sổ sang phải
if (right >= k - 1) { // cửa sổ đủ k phần tử
maxSum = Math.max(maxSum, windowSum)
windowSum -= nums[left] // thu nhỏ từ trái
left++
}
}
return maxSum
}Cách tối ưu dùng Cửa sổ trượt (Sliding Window) kích thước cố định k: mỗi bước cộng phần tử mới vào phải, trừ phần tử cũ ở trái.
Không cộng lại từ đầu, mỗi phần tử chỉ xử lý đúng 1 lần.
Chạy thử từng bước
1function maxSubarrayOfSizeK(nums: number[], k: number): number {2let windowSum = 03let maxSum = -Infinity4let left = 05for (let right = 0; right < nums.length; right++) {6windowSum += nums[right] // mở rộng cửa sổ sang phải7if (right >= k - 1) { // cửa sổ đủ k phần tử8maxSum = Math.max(maxSum, windowSum)9windowSum -= nums[left] // thu nhỏ từ trái10left++11}12}13return maxSum14}
Trường hợp biên phải nhớ
k bằng độ dài mảng — cả mảng là một cửa sổ duy nhất, trả về tổng toàn bộ mảng.
k=1 — trả về phần tử lớn nhất trong mảng.
Tất cả phần tử âm — vẫn chạy đúng vì maxSum khởi đầu từ -Infinity.
k lớn hơn độ dài mảng — điều kiện if (right >= k-1) không bao giờ đúng, maxSum không được cập nhật (trả về -Infinity); cần validate k ≤ n trước.