Maximum Sum Subarray of Size K

Q: Độ phức tạp thời gian của bài toán tìm mảng con có tổng lớn nhất với kích thước k là bao nhiêu?

Với kỹ thuật cửa sổ trượt, độ phức tạp thời gian là O(n) và độ phức tạp không gian phụ là O(1) : tính tổng cho cửa sổ đầu tiên, sau đó cộng một lần và trừ một lần ở mỗi bước. Tính riêng tổng của từng cửa sổ có độ phức tạp O(n·k) .

Q: Điều này khác gì so với bài toán mảng con có tổng lớn nhất?

Ở đây, độ dài được cố định ở k , nên tổng trượt sẽ bao quát mọi ứng viên. Trong bài toán mảng con có tổng lớn nhất, độ dài không cố định, và thuật toán Kadane sẽ quyết định tại mỗi phần tử xem nên kéo dài đoạn hiện tại hay bắt đầu một đoạn mới. Một cửa sổ cố định không có lựa chọn đó.

Q: Liệu tổng tiền tố cũng giải được bài này không?

Đúng. Gọi prefix[i] là tổng của i phần tử đầu tiên; cửa sổ bắt đầu tại s có tổng là prefix[s+k] - prefix[s] . Cách này cũng mất thời gian O(n) , nhưng lưu n+1 tổng, trong khi cửa sổ trượt chỉ cần hai biến.

DễCửa sổ trượt

+10

Bạn nhận được một mảng số nguyên nums và độ dài cửa sổ k. Xét mọi dãy gồm đúng k phần tử liền kề và trả về tổng lớn nhất trong các dãy đó. Các giá trị có thể âm, vì vậy đáp án cũng có thể âm.

Hàm

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: mảng số nguyên
kinteger: số phần tử lân cận mà mỗi cửa sổ chứa
Trả vềinteger: tổng lớn nhất của bất kỳ k phần tử liên tiếp nào

Ràng buộc

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Ví dụ

Đầu vào: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Đầu ra: 10
Giải thích: Năm cửa sổ có độ dài 3 có tổng lần lượt là 6, 9, 8, 10 và 4. Tổng lớn nhất là 7 + (-2) + 5 = 10.

Đầu vào: nums = [-3, -8, -1, -6]k = 2
Đầu ra: -7
Giải thích: Mọi giá trị đều âm, nên tổng của mỗi cửa sổ cũng vậy: -11, -9 và -7. Tổng lớn nhất là -1 + (-6) = -7.

Đầu vào: nums = [5, -2, 4]k = 3
Đầu ra: 7
Giải thích: Khi k bằng độ dài của mảng, có một cửa sổ, chính là toàn bộ mảng, và 5 + (-2) + 4 = 7.

Câu hỏi mở rộng

Bạn cũng có thể trả về vị trí bắt đầu của cửa sổ tốt nhất, chọn cửa sổ ở bên trái nhất nếu có nhiều cửa sổ bằng nhau không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Có n-k+1 cửa sổ, và tính tổng từng cửa sổ từ đầu cần k phép cộng. Các cửa sổ liền kề chỉ khác nhau ở hai phần tử, vì vậy hãy trượt cửa sổ thay vì tính lại từ đầu: một giá trị đi vào, một giá trị đi ra, và mỗi tổng mới chỉ cần hai phép toán.

Cộng tất cả các cửa sổ

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Một cửa sổ được xác định bởi vị trí bắt đầu, từ chỉ số 0 đến n-k; nếu bắt đầu muộn hơn, cửa sổ sẽ vượt quá phần cuối. Với mỗi vị trí bắt đầu, hãy cộng k phần tử rồi so sánh tổng đó với tổng lớn nhất tính đến lúc này. Vì mọi cửa sổ đều được kiểm tra nên ta sẽ tìm được cửa sổ có tổng lớn nhất.

Chi phí là (n-k+1) × k phép cộng, lớn nhất khi k xấp xỉ một nửa n: 5001 × 5000, khoảng 2.5 × 10^7, với n = 10^4 và k = 5000. Hầu hết các phép cộng này lặp lại công việc đã thực hiện cho cửa sổ trước đó.

Thuật toán

Đặt best thành giá trị nhỏ nhất có thể.
Với mỗi giá trị start từ 0 đến n-k, đặt total = 0.
Cộng nums[start] đến nums[start+k-1] vào total.
Nếu total lớn hơn best, hãy lưu giá trị đó.
Trả về best.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Trượt một cửa sổ cố định

Ý tưởng

Trong ví dụ đầu tiên, các cửa sổ bắt đầu ở vị trí 0 và 1 có tổng lần lượt là 6 và 9. Cả hai đều chứa -1 và 3, vì vậy tổng thứ hai bằng tổng thứ nhất cộng với 7 vừa đi vào rồi trừ đi 4 vừa rời khỏi: 6 + 7 - 4 = 9.

Điều này đúng ở mỗi bước. Khi đầu bên phải di chuyển đến chỉ số i, nums[i] đi vào và nums[i-k] rời khỏi. Tính tổng của cửa sổ đầu tiên một lần, sau đó cập nhật tổng bằng một phép cộng và một phép trừ ở mỗi bước, rồi giữ lại tổng lớn nhất bạn thấy.

Thuật toán

Cộng các phần tử từ nums[0] đến nums[k-1] vào window.
Đặt best = window.
Với mỗi i từ k đến n-1, cộng nums[i] và trừ nums[i-k].
Sau mỗi bước, đặt best bằng giá trị lớn hơn giữa best và window.
Trả về best.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Lỗi thường gặp và trường hợp biên

Khởi tạo best bằng 0. Với [-3, -8, -1, -6] và k = 2, giá trị này không bao giờ bị vượt qua, nên bạn trả về 0 thay vì -7.
Trừ sai phần tử. Khi nums[i] đi vào, nums[i-k] rời khỏi cửa sổ; dùng nums[i-k+1] hoặc nums[i-k-1] sẽ tạo ra cửa sổ có độ dài sai.
Dừng sớm hơn một vị trí bắt đầu. Cửa sổ cuối cùng bắt đầu tại n-k. Với [5, -2, 4] và k = 3, đây là cửa sổ duy nhất, và lỗi lệch một vị trí sẽ trả về giá trị khởi tạo của best.
Chỉ so sánh bên trong vòng lặp. Với [9, 1, 1] và k = 2, cửa sổ đầu tiên có tổng là 10 và là cửa sổ tốt nhất, vì vậy hãy gán best bằng giá trị đó trước vòng lặp.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán tìm mảng con có tổng lớn nhất với kích thước k là bao nhiêu?

Với kỹ thuật cửa sổ trượt, độ phức tạp thời gian là O(n) và độ phức tạp không gian phụ là O(1): tính tổng cho cửa sổ đầu tiên, sau đó cộng một lần và trừ một lần ở mỗi bước. Tính riêng tổng của từng cửa sổ có độ phức tạp O(n·k).

Điều này khác gì so với bài toán mảng con có tổng lớn nhất?

Ở đây, độ dài được cố định ở k, nên tổng trượt sẽ bao quát mọi ứng viên. Trong bài toán mảng con có tổng lớn nhất, độ dài không cố định, và thuật toán Kadane sẽ quyết định tại mỗi phần tử xem nên kéo dài đoạn hiện tại hay bắt đầu một đoạn mới. Một cửa sổ cố định không có lựa chọn đó.

Liệu tổng tiền tố cũng giải được bài này không?

Đúng. Gọi prefix[i] là tổng của i phần tử đầu tiên; cửa sổ bắt đầu tại s có tổng là prefix[s+k] - prefix[s]. Cách này cũng mất thời gian O(n), nhưng lưu n+1 tổng, trong khi cửa sổ trượt chỉ cần hai biến.

def maxSumSubarray(nums, k):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Đầu ra mong đợi