Maximum Product Subarray

+10

Nhân các phần tử trong một mảng con của nums với nhau, rồi trả về tích lớn nhất mà bất kỳ mảng con nào có thể tạo ra. Mảng con gồm các phần tử liên tiếp, không có khoảng trống và không bao giờ rỗng, vì vậy ngay cả một mảng chỉ có số âm cũng có đáp án. Có thể có các giá trị bằng 0 và giá trị âm.

Hàm

maxProduct(nums: integer-array) → integer

numsinteger-array: các số nguyên cần nhân với nhau, mỗi số nằm trong khoảng từ -10 đến 10
Trả vềinteger: tích lớn nhất của một mảng con không rỗng

Ràng buộc

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
Tích của mọi mảng con nằm trong phạm vi số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: nums = [2, -5, 3, -2, 0, 4]
Đầu ra: 60
Giải thích: Hai số âm triệt tiêu lẫn nhau: 2 × -5 × 3 × -2 = 60. Số 0 chia mảng thành hai phần, còn số 4 ở phía bên kia không thể lớn hơn 60.

Đầu vào: nums = [-2, 3, -4, -1]
Đầu ra: 24
Giải thích: Tích của toàn bộ mảng là -24 vì mảng có ba số âm. Bỏ phần tử cuối cùng thì còn lại hai số âm: -2 × 3 × -4 = 24, lớn hơn 12 thu được khi bỏ phần tử đầu tiên.

Đầu vào: nums = [-6, 0, -7]
Đầu ra: 0
Giải thích: Mảng con không chứa số 0 chỉ gồm một số âm, còn mảng con chứa số 0 có tích bằng 0. Lựa chọn tốt nhất là mảng con [0].

Câu hỏi mở rộng

Bạn sẽ báo thêm vị trí bắt đầu và kết thúc của mảng con tốt nhất như thế nào, vẫn trong thời gian O(n) và không gian O(1)?

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

Nhân với một số âm sẽ đảo ngược thứ tự các tích, vì vậy tích nhỏ nhất tính đến lúc đó có thể trở thành tích lớn nhất ở bước tiếp theo, còn số không sẽ xóa mọi tích. Ở mỗi chỉ số, hãy lưu hai giá trị thay vì một: tích lớn nhất và nhỏ nhất của mảng con kết thúc tại đó. Chỉ cần duyệt một lần.

Nhân mọi mảng con bắt đầu từ mỗi vị trí

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

Ý tưởng

Cố định chỉ số bắt đầu và dịch chỉ số kết thúc sang phải, nhân product đang có với mỗi phần tử mới. So sánh tích này với tích lớn nhất sau mỗi bước giúp xét mỗi mảng con đúng một lần. Đặt best thành nums[0], vì đáp án có thể là số âm.

Có khoảng n²/2 cặp chỉ số bắt đầu và kết thúc, mỗi cặp cần một phép nhân: 2 × 10^8 cho 20,000 phần tử.

Thuật toán

Gán best bằng nums[0].
Với mỗi start, gán product bằng 1.
Di chuyển end từ start đến chỉ số cuối cùng và nhân product với nums[end].
Nếu product lớn hơn best, hãy lưu giá trị đó.
Trả về best.

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

Quét từ cả hai đầu, bắt đầu lại khi gặp số 0

Ý tưởng

Số 0 chia mảng thành các đoạn liên tiếp không chứa số 0. Trong mỗi đoạn, mọi giá trị đều có độ lớn ít nhất là 1, vì vậy mảng con dài hơn không bao giờ có tích tuyệt đối nhỏ hơn, chỉ có dấu là thay đổi. Nếu có số lượng số âm chẵn, toàn bộ đoạn là lựa chọn tốt nhất. Nếu có số lượng số âm lẻ, phải bỏ đi một số âm; cách cắt tốt nhất là bỏ số âm đầu tiên và mọi phần tử trước nó, hoặc bỏ số âm cuối cùng và mọi phần tử sau nó. Dù chọn cách nào, bạn vẫn giữ lại một hậu tố hoặc một tiền tố của đoạn.

Một lượt duyệt từ trái sang phải với tích lũy kiểm tra mọi tiền tố, đặt lại tích bằng 1 sau mỗi số 0. Một lượt duyệt từ phải sang trái kiểm tra mọi hậu tố. Với [-2, 3, -4, -1], lượt duyệt từ trái sang phải lần lượt cho kết quả -2, -6, 24 và -24; lượt duyệt từ phải sang trái cho kết quả -1, 4, 12 và -24, vì vậy đáp án là 24. Lập luận này cần mọi giá trị khác 0 có độ lớn ít nhất là 1, điều này đúng với các số nguyên.

Thuật toán

Đặt best thành nums[0] và product thành 1.
Duyệt từ trái sang phải: nhân product với từng phần tử và giữ lại giá trị lớn hơn giữa best và product.
Mỗi khi product trở thành 0, đặt lại thành 1 để lần duyệt tiếp theo bắt đầu mới.
Đặt lại product thành 1 rồi duyệt tương tự từ phải sang trái.
Trả về best.

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

Theo dõi tích lớn nhất và nhỏ nhất kết thúc tại đây

Ý tưởng

Mọi mảng con kết thúc ở chỉ số i đều là riêng nums[i], hoặc bằng nums[i] nhân với một mảng con kết thúc ở i-1. Khi nums[i] âm, tích lớn nhất trong các tích đó đến từ tích nhỏ nhất kết thúc ở i-1. Vì vậy, hãy giữ cả hai giá trị: high và low, lần lượt là tích lớn nhất và nhỏ nhất của một mảng con kết thúc ở chỉ số hiện tại. high mới là giá trị lớn nhất trong num, high × num và low × num, còn low mới là giá trị nhỏ nhất. Chọn riêng num sẽ bắt đầu lại dãy sau số 0.

Trong ví dụ đầu tiên, low là -30 khi -2 xuất hiện, và -30 × -2 = 60 trở thành high, tức là đáp án.

Thuật toán

Đặt high, low và best bằng nums[0].
Với mỗi phần tử tiếp theo num, tính a = high × num và b = low × num.
Đặt high bằng giá trị lớn nhất và low bằng giá trị nhỏ nhất trong num, a và b.
Đặt best bằng giá trị lớn hơn giữa best và high.
Trả về best.

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

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

Chỉ theo dõi tích lớn nhất. Với ví dụ đầu tiên, cách này trả về 4 thay vì 60 vì nó bỏ qua giá trị -30, vốn trở thành 60 khi nhân với -2.
Tính low mới từ high đã được cập nhật. Lưu high × num và low × num trước khi thay đổi một trong hai.
Khởi tạo best bằng 0 hoặc 1. [-3] phải trả về -3 vì mảng con không thể rỗng.
Chỉ chạy lượt duyệt từ trái sang phải trong phương pháp hai lượt. Với [-2, 3, 4], cách này không bao giờ thấy giá trị nào lớn hơn -2, nhưng hậu tố [3, 4] cho tích 12.
Trong JavaScript, TypeScript và Lua, 0 nhân với một số âm sẽ cho kết quả là -0, được in ra kèm dấu trừ. Hãy cộng 0 vào kết quả trước khi trả về.

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

Độ phức tạp thời gian của bài toán mảng con có tích lớn nhất là gì?

Theo dõi tích lớn nhất và nhỏ nhất kết thúc tại mỗi chỉ số mất O(n) thời gian và O(1) bộ nhớ. Phương pháp hai lượt dùng tiền tố và hậu tố cũng có độ phức tạp tương tự. Nhân các phần tử trong mọi mảng con bắt đầu tại mỗi vị trí mất O(n²) thời gian.

Tại sao cần giá trị nhỏ nhất trong bài toán mảng con có tích lớn nhất?

Một số âm biến tích âm nhất kết thúc tại chỉ số trước đó thành tích lớn nhất. Nếu chỉ giữ lại tích lớn nhất, bạn sẽ không còn ứng viên đó khi cần đến. Trong [3, -2, -4], tích nhỏ nhất trước -4 là -6, và -6 × -4 = 24 là đáp án.

Maximum Product Subarray khác Maximum Subarray như thế nào?

Với phép tính tổng, tổng tích lũy âm chỉ làm kết quả tệ hơn, nên mỗi chỉ số chỉ cần một giá trị. Với phép tính tích, giá trị tích lũy âm có thể trở thành lớn nhất sau khi nhân với một số âm khác, còn số 0 sẽ đặt lại mọi thứ. Vì vậy, phiên bản tính tích giữ lại tích lớn nhất và nhỏ nhất tại mỗi chỉ số.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [2, -5, 3, -2, 0, 4]

Đầu ra mong đợi

Maximum Product Subarray

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Nhân mọi mảng con bắt đầu từ mỗi vị trí

Quét từ cả hai đầu, bắt đầu lại khi gặp số 0

Theo dõi tích lớn nhất và nhỏ nhất kết thúc tại đây

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

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

Bài tập tương tự