Theo Dõi Cả Min Lẫn Max: Tại Sao Bài Tích Lớn Nhất Phá Vỡ Thuật Toán Kadane Thông Thường

Ngay khi một số âm xuất hiện trong input, thuật toán Kadane tiêu chuẩn — cái đã giải Maximum Subarray trong O(n) — bắt đầu sai. Âm nhân âm ra dương, nghĩa là running product tệ nhất tại vị trí i có thể trở thành running product tốt nhất tại vị trí i+1. Kadane thông thường chỉ theo dõi một giá trị mỗi vị trí. Bài này cần hai.

Đó là toàn bộ insight. Mọi thứ còn lại đều xuất phát từ đây.

Những gì constraints buộc bạn làm

1 <= nums.length <= 2 × 10^4 và -10 <= nums[i] <= 10. Giới hạn độ dài loại bỏ O(n²) ở bất kỳ quy mô nào nghiêm túc — hai mươi nghìn phần tử có nghĩa là bốn trăm triệu phép nhân ở brute force, rõ ràng không phải hướng đi. Khoảng giá trị nhỏ: từ -10 đến 10, và bài đảm bảo kết quả fit trong 32-bit integer, nên không có nguy cơ overflow.

Constraint tôi quan tâm nhất là khoảng âm. Một phần tử -10 có thể biến running product -100 thành +1000. Đây là căng thẳng cốt lõi: bạn không thể loại bỏ một running product âm theo kiểu Kadane loại bỏ running sum âm, vì running product âm đó có thể là chính xác thứ phần tử âm tiếp theo cần. Thuật toán phải duy trì nhận thức về cả hai thái cực.

Brute force: thử mọi subarray

Trước khi làm gì phức tạp, hướng tiếp cận trực tiếp: với mỗi starting index i, mở rộng sang phải và theo dõi running product. Kiểm tra tất cả n(n+1)/2 subarray.

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        n = len(nums)
        result = nums[0]
        for i in range(n):
            product = 1
            for j in range(i, n):
                product *= nums[j]
                result = max(result, product)
        return result

public class Solution {
    public int MaxProduct(int[] nums) {
        int n = nums.Length;
        int result = nums[0];
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = i; j < n; j++) {
                product *= nums[j];
                result = Math.Max(result, product);
            }
        }
        return result;
    }
}

O(n²) time, O(1) space. Hoạt động đúng và xử lý tất cả edge case — vòng lặp ngoài đảm bảo các subarray một phần tử được xét, bao gồm trường hợp toàn số âm mà đáp án là phần tử lớn nhất đơn lẻ. Vấn đề thuần túy là tốc độ: với n = 20,000 thì đây là 200 triệu phép nhân. Ổn với input nhỏ, không phù hợp thực tế.

DP hai trạng thái

Quan sát then chốt: tại mỗi vị trí i, tích lớn nhất của bất kỳ subarray nào kết thúc tại i là một trong ba thứ — nums[i] đứng một mình, max_so_far * nums[i], hoặc min_so_far * nums[i]. Lựa chọn thứ ba là lý do bài này khác Maximum Subarray. Khi nums[i] âm, nhân nó với running product âm nhất cho ra kết quả dương nhất.

Vậy chúng ta theo dõi hai running value: max_prod (tích tốt nhất kết thúc tại index hiện tại) và min_prod (tích tệ nhất kết thúc tại index hiện tại). Tại mỗi bước:

new_max = max(nums[i], max_prod * nums[i], min_prod * nums[i])
new_min = min(nums[i], max_prod * nums[i], min_prod * nums[i])

Đáp án toàn cục là running maximum của tất cả các giá trị max_prod.

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        max_prod = nums[0]
        min_prod = nums[0]
        result = nums[0]
 
        for i in range(1, len(nums)):
            candidates = (nums[i], max_prod * nums[i], min_prod * nums[i])
            max_prod = max(candidates)
            min_prod = min(candidates)
            result = max(result, max_prod)
 
        return result

public class Solution {
    public int MaxProduct(int[] nums) {
        int maxProd = nums[0];
        int minProd = nums[0];
        int result = nums[0];
 
        for (int i = 1; i < nums.Length; i++) {
            int a = nums[i];
            int b = maxProd * nums[i];
            int c = minProd * nums[i];
            maxProd = Math.Max(a, Math.Max(b, c));
            minProd = Math.Min(a, Math.Min(b, c));
            result = Math.Max(result, maxProd);
        }
 
        return result;
    }
}

O(n) time, O(1) space. Ba phép so sánh mỗi phần tử, bộ nhớ hằng bất kể kích thước input. Đây là thứ tôi sẽ ship.

Một số implementation dùng kỹ thuật swap — nếu nums[i] < 0, hoán đổi max_prod và min_prod trước khi nhân. Cách đó cũng đúng và thể hiện rõ logic đảo dấu hơn, nhưng lấy max và min của cả ba candidates xử lý được mà không cần nhánh điều kiện. Tôi thích dạng ba candidates hơn vì nó đọc như một ý duy nhất thay vì một phép biến đổi có điều kiện.

Trace qua [2, 3, -2, 4]

Ví dụ trong đề bài. Đi từng bước.

Tại i=0: khởi tạo mọi thứ là 2. Result là 2.

Tại i=1, nums[1] = 3. Candidates: 3, 2×3=6, 2×3=6. max_prod = 6, min_prod = 3. Result thành 6.

Tại i=2, nums[2] = -2. Candidates: -2, 6×(-2)=-12, 3×(-2)=-6. max_prod = -2, min_prod = -12. Đây là bước thú vị — running maximum rớt xuống âm vì mọi subarray kết thúc ở đây mà bao gồm các phần tử trước đều cho tích âm. Result giữ nguyên 6.

Tại i=3, nums[3] = 4. Candidates: 4, (-2)×4=-8, (-12)×4=-48. max_prod = 4, min_prod = -48. Result giữ nguyên 6.

Đáp án là 6, từ subarray [2, 3]. Lưu ý min_prod tại i=3 là -48 — nếu mảng tiếp tục với -1, bước tiếp theo sẽ cho max_prod = 48, vượt qua 6.

Edge case và lý do code xử lý được

Một phần tử duy nhất. Khởi tạo về nums[0], vòng lặp không chạy. Trả về phần tử duy nhất. Đúng — một phần tử là subarray hợp lệ.

Toàn số âm, ví dụ [-3, -2, -1]. Tại i=0, cả hai tracker bắt đầu ở -3. Tại i=1: candidates là -2, (-3)×(-2)=6, (-3)×(-2)=6. max_prod = 6, min_prod = -2. Result là 6. Đúng — [-3, -2] cho tích lớn nhất.

Số 0 trong mảng, ví dụ [2, -3, 0, 4]. Khi nums[i] = 0, tất cả candidates đều về phía 0. Cả hai tracker reset về 0, nghĩa là bắt đầu subarray mới sau số 0. Phần tử 4 sau đó tự thành subarray và cho max_prod = 4. Đây chính xác là lý do chúng ta thêm nums[i] đứng một mình vào candidates — nó cho phép thuật toán restart.

[-2, 0, -1] từ đề bài. Kết quả nên là 0, không phải 2. Tại i=1, số 0 reset cả hai tracker về 0. Tại i=2, candidates là -1, 0×(-1)=0, 0×(-1)=0. max_prod = 0. Result giữ nguyên 0. Hai phần tử [-2, -1] không liên tiếp nhau — bị ngăn cách bởi 0 — nên thuật toán không bao giờ nhân chúng với nhau, đúng như yêu cầu.

So sánh độ phức tạp

Cả hai approach đều dùng O(1) space, đặc tính đẹp của bài này. DP table về mặt khái niệm tồn tại (một entry mỗi index, hai giá trị mỗi entry), nhưng bạn không bao giờ cần lưu toàn bộ — chỉ cần giá trị bước hiện tại.

Mental model và nơi nó xuất hiện

Pattern ở đây là two-lookback DP với nhận thức về dấu. Bạn duy trì hai running value thay vì một vì phép toán (nhân) không đơn điệu với input dương/âm. Phép cộng thì đơn điệu: một số hạng âm luôn làm tổng nhỏ hơn, nên Kadane loại nó bằng cách reset về phần tử hiện tại. Phép nhân không như vậy: một thừa số âm có thể làm tích lớn hơn nếu running product đang âm.

Bất cứ khi nào bạn thấy "maximum/minimum trên subarray liên tiếp" kết hợp với phép toán có thể đảo dấu, hãy nghĩ xem bạn có cần một minimum tracker song song với maximum hay không.

Những bài liên quan đáng làm sau bài này:

• LeetCode 53, Maximum Subarray — phiên bản phép cộng, chỉ cần một tracker. Nên làm trước để hiểu tại sao phiên bản tích cần nhiều hơn.
• LeetCode 238, Product of Array Except Self — không có phép chia, dùng prefix/suffix products, khác flavor nhưng cùng ý tưởng "nghĩ về tích theo cách khác".
• LeetCode 628, Maximum Product of Three Numbers — cửa sổ cố định nhỏ thay vì subarray biến đổi; có thể sort hoặc chỉ track hai số âm lớn nhất và ba số dương lớn nhất.
• LeetCode 1567, Maximum Length of Subarray With Positive Product — cùng intuition theo dõi dấu, mục tiêu khác: độ dài thay vì giá trị.

Bước nhảy từ Maximum Subarray (53) sang bài này (152) chính xác là bước nhảy từ Kadane một trạng thái sang Kadane hai trạng thái. House Robber (198) là một bài khác trong series cũng dùng two-lookback state, nhưng transition DP ở đó được điều khiển bởi parity index thay vì dấu. Nhận ra hình dạng chung giữa các bài này là thứ làm mental model có thể chuyển đổi được.