Maximum Subarray

+10

Bạn nhận được một danh sách số nguyên nums. Mảng con (subarray) là một đoạn gồm các phần tử liền kề, không có khoảng trống, và phải chứa ít nhất một phần tử. Hãy trả về tổng lớn nhất mà bất kỳ mảng con nào của nums có thể đạt được. Bạn chỉ trả về tổng, không trả về chính mảng con.

Hàm

maxSubArray(nums: integer-array) → integer

numsinteger-array: danh sách số nguyên có ít nhất một phần tử
Trả vềinteger: tổng lớn nhất của một dãy không rỗng gồm các phần tử liền kề

Ràng buộc

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
Đáp án luôn nằm trong phạm vi số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: nums = [2, -4, 3, -1, 5, -6, 1]
Đầu ra: 7
Giải thích: Dãy [3, -1, 5] có tổng bằng 7. Kéo dài sang trái thì cộng thêm -4 rồi 2, tổng cộng giảm 2. Kéo dài sang phải thì cộng thêm -6 rồi 1, tổng cộng giảm 5. Không có dãy nào khác cho kết quả tốt hơn.

Câu hỏi mở rộng

Bạn cũng có thể giải bài toán bằng phương pháp chia để trị trong O(n log n), chia danh sách làm đôi và xử lý các dãy liên tiếp băng qua điểm giữa không?

Lời giải

Một danh sách gồm n số có khoảng n²/2 mảng con, quá nhiều để kiểm tra từng mảng một khi có 10^5 phần tử. Phần khó là xử lý các số âm: một đoạn nên giữ lại phần tử âm nếu các phần tử phía sau bù lại được, và bỏ mọi thứ trước nó nếu không. Thuật toán Kadane đưa ra lựa chọn đó tại mỗi phần tử chỉ với một phép so sánh.

Tính tổng mọi mảng con

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

Ý tưởng

Mỗi mảng con có chỉ số đầu tiên là left và chỉ số cuối cùng là right, vì vậy thử mọi cặp sẽ tìm được cặp tốt nhất. Cố định left rồi tăng dần right, cộng từng phần tử mới vào total đang tích lũy: mỗi mảng con chỉ cần một phép cộng, không cần vòng lặp thứ ba.

Như vậy vẫn còn khoảng n²/2 cặp, tương đương năm tỷ phép cộng với 10^5 phần tử.

Thuật toán

Đặt best bằng phần tử đầu tiên.
Với mỗi chỉ số bắt đầu left, đặt total đang chạy về 0.
Di chuyển right từ left đến cuối danh sách và cộng nums[right] vào total.
Sau mỗi lần cộng, lưu total vào best nếu giá trị này lớn hơn.
Trả về best.

def maxSubArray(nums):
    best = nums[0]
    for left in range(len(nums)):
        total = 0
        # Grow the subarray that starts at left by one element at a time
        for right in range(left, len(nums)):
            total += nums[right]
            best = max(best, total)
    return best

Thuật toán Kadane

Ý tưởng

Đoạn chạy tốt nhất kết thúc tại chỉ số i là riêng nums[i], hoặc đoạn chạy tốt nhất kết thúc tại i-1 rồi thêm nums[i] vào, vì không có đoạn chạy nào khác kết thúc tại i-1 có tổng lớn hơn. Vì vậy, hãy lưu một giá trị, endingHere, là tổng lớn nhất của đoạn chạy kết thúc tại phần tử hiện tại. Ở phần tử tiếp theo x, giá trị này trở thành số lớn hơn giữa x và endingHere + x: khi tổng của đoạn chạy còn dương, bạn mở rộng đoạn đó; khi tổng bằng không hoặc âm, bạn bắt đầu lại từ x.

Mảng con tốt nhất sẽ kết thúc ở đâu đó, nên đáp án là giá trị lớn nhất mà endingHere nhận được. Trong ví dụ đầu tiên, giá trị này lần lượt là 2, -2, 3, 2, 7, 1, 2, và đáp án là 7.

Thuật toán

Đặt endingHere và best bằng phần tử đầu tiên.
Với mỗi phần tử tiếp theo x, đặt endingHere bằng giá trị lớn hơn giữa x và endingHere + x.
Đặt best bằng giá trị lớn hơn giữa best và endingHere.
Sau phần tử cuối cùng, trả về best.

def maxSubArray(nums):
    current = nums[0]
    best = nums[0]
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    return best

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

Bắt đầu best bằng 0. Khi đó, [-3, -1, -2] trả về 0 thay vì -1. Hãy bắt đầu từ phần tử đầu tiên.
Giới hạn tổng đang tính bằng max(0, endingHere + x). Cách này cũng thất bại với cùng danh sách đó; hãy so sánh với x.
Chỉ cộng các số dương. Các phần tử phải nằm cạnh nhau, vì vậy ví dụ đầu tiên cho kết quả 7, không phải 2 + 3 + 5 + 1 = 11.
Bắt đầu vòng lặp ở chỉ số 1 mà không gán endingHere và best bằng nums[0]. Danh sách chỉ có một phần tử, chẳng hạn [-5], phải trả về -5.

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

Kadane's algorithm là gì?

Thuật toán Kadane tìm tổng lớn nhất của một mảng con liên tiếp chỉ trong một lượt duyệt. Thuật toán giữ lại tổng lớn nhất của một đoạn kết thúc tại phần tử hiện tại. Với mỗi phần tử mới, thuật toán sẽ nối dài đoạn đó hoặc bắt đầu một đoạn mới. Tổng lớn nhất trong các tổng này chính là đáp án.

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

Thuật toán Kadane có độ phức tạp thời gian O(n) và cần O(1) bộ nhớ bổ sung, vì thuật toán chỉ xét mỗi phần tử một lần. Kiểm tra mọi mảng con bằng tổng tích lũy cần O(n²), còn tính lại tổng từ đầu cho mỗi mảng con cần O(n³).

Tại sao bài toán mảng con lớn nhất là một bài toán quy hoạch động?

Tổng lớn nhất của một đoạn kết thúc tại chỉ số i chỉ phụ thuộc vào tổng lớn nhất của một đoạn kết thúc tại i-1. Đó là một công thức truy hồi trên các chỉ số, đặc trưng của quy hoạch động. Thuật toán Kadane chỉ giữ giá trị mới nhất thay vì cả một bảng, nên chỉ cần O(1) bộ nhớ.

def maxSubArray(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

nums = [2, -4, 3, -1, 5, -6, 1]

Đầu ra mong đợi