Định nghĩa bài toán
Cho một mảng số nguyên nums, hãy tìm dãy con liên tiếp (contiguous subarray) có tổng lớn nhất và trả về giá trị tổng đó. Dãy con phải chứa ít nhất một phần tử.
Ví dụ:
nums = [-2,1,-3,4,-1,2,1,-5,4] → Kết quả: 6 (dãy con [4,-1,2,1] có tổng lớn nhất).
nums = [1] → Kết quả: 1 (dãy con [1]).
nums = [5,-3,5] → Kết quả: 7 (dãy con [5,-3,5] hoặc [5]).
nums = [-1] → Kết quả: -1 (dãy con [-1]).
Ràng buộc:
Mảng có độ dài từ 1 đến 10^5.
Giá trị các phần tử trong mảng nằm trong khoảng [-10^4, 10^4].
Luôn có ít nhất một phần tử trong mảng.
Các cách tiếp cận giải quyết
Bài toán này có thể được giải bằng nhiều phương pháp, từ cách đơn giản nhưng kém hiệu quả đến các cách tối ưu hơn như thuật toán Kadane. Dưới đây là các cách tiếp cận phổ biến:
1. Brute Force
Kiểm tra tất cả các dãy con liên tiếp và tính tổng của chúng để tìm tổng lớn nhất.
Thuật toán:
Duyệt qua tất cả các cặp chỉ số (i, j) đại diện cho các dãy con từ i đến j.
Tính tổng của dãy con nums[i:j+1].
Cập nhật tổng lớn nhất nếu tổng hiện tại lớn hơn.
def maxSubArray(nums: list[int]) -> int: max_sum = nums[0] for i in range(len(nums)): current_sum = 0 for j in range(i, len(nums)): current_sum += nums[j] max_sum = max(max_sum, current_sum) return max_sum
Ưu điểm: Đơn giản, dễ hiểu, đảm bảo tìm được kết quả đúng.
Nhược điểm: Rất chậm với mảng lớn, không khả thi trong phỏng vấn.
Độ phức tạp:
Thời gian: O(n²) (duyệt tất cả dãy con).
Không gian: O(1) (chỉ lưu biến tổng).
2. Thuật toán Kadane (Dynamic Programming)
Sử dụng thuật toán Kadane để tìm tổng lớn nhất một cách hiệu quả bằng cách duy trì tổng tối đa tại mỗi vị trí.
Thuật toán:
Khởi tạo hai biến: max_sum (tổng lớn nhất toàn cục) và current_sum (tổng dãy con hiện tại).
Duyệt qua mảng:
Với mỗi phần tử, cập nhật current_sum bằng cách lấy tối đa giữa phần tử hiện tại và tổng current_sum + nums[i].
Cập nhật max_sum nếu current_sum lớn hơn.
Trả về max_sum.
def maxSubArray(nums: list[int]) -> int: max_sum = nums[0] current_sum = nums[0] for i in range(1, len(nums)): current_sum = max(nums[i], current_sum + nums[i]) max_sum = max(max_sum, current_sum) return max_sum
Ưu điểm: Hiệu quả, được sử dụng rộng rãi trong phỏng vấn, dễ triển khai.
Nhược điểm: Cần hiểu rõ cách hoạt động của thuật toán động.
Độ phức tạp:
Thời gian: O(n) (duyệt mảng một lần).
Không gian: O(1) (chỉ dùng hai biến).
3. Chia để trị (Divide and Conquer)
Chia mảng thành các phần nhỏ hơn và tìm tổng lớn nhất bằng cách kết hợp kết quả từ các nửa.
Thuật toán:
Chia mảng thành hai nửa trái và phải tại điểm giữa.
Đệ quy tìm tổng lớn nhất của:
Dãy con bên trái.
Dãy con bên phải.
Dãy con chứa điểm giữa (tính tổng từ giữa sang trái và từ giữa sang phải).
Trả về giá trị lớn nhất trong ba trường hợp trên.
def maxSubArray(nums: list[int]) -> int: def maxCrossingSum(nums, left, mid, right): left_sum = float('-inf') current_sum = 0 for i in range(mid, left - 1, -1): current_sum += nums[i] left_sum = max(left_sum, current_sum) right_sum = float('-inf') current_sum = 0 for i in range(mid + 1, right + 1): current_sum += nums[i] right_sum = max(right_sum, current_sum) return left_sum + right_sum def maxSubArrayHelper(nums, left, right): if left == right: return nums[left] mid = (left + right) // 2 return max( maxSubArrayHelper(nums, left, mid), maxSubArrayHelper(nums, mid + 1, right), maxCrossingSum(nums, left, mid, right) ) return maxSubArrayHelper(nums, 0, len(nums) - 1)
Ưu điểm: Thể hiện tư duy đệ quy và chia để trị, phù hợp với các bài toán phức tạp hơn.
Nhược điểm: Phức tạp hơn Kadane, không tối ưu về thời gian.
Độ phức tạp:
Thời gian: O(n log n) (do chia đệ quy và tính tổng qua điểm giữa).
Không gian: O(log n) (do ngăn xếp đệ quy).
4. Sử dụng mảng tiền tố (Prefix Sum - Biến thể)
Tính tổng tiền tố để tìm tất cả các dãy con và tổng lớn nhất.
Thuật toán:
Tạo mảng tiền tố prefix_sum sao cho prefix_sum[i] là tổng từ nums[0] đến nums[i-1].
Duyệt qua các cặp chỉ số (i, j) để tính tổng dãy con từ i đến j bằng prefix_sum[j+1] - prefix_sum[i].
Theo dõi tổng lớn nhất.
def maxSubArray(nums: list[int]) -> int: prefix_sum = [0] * (len(nums) + 1) for i in range(len(nums)): prefix_sum[i + 1] = prefix_sum[i] + nums[i] max_sum = nums[0] for i in range(len(nums)): for j in range(i, len(nums)): current_sum = prefix_sum[j + 1] - prefix_sum[i] max_sum = max(max_sum, current_sum) return max_sum
Ưu điểm: Dễ hiểu, có thể áp dụng cho các bài toán liên quan đến tổng dãy con.
Nhược điểm: Tốn thời gian tương tự lực đục, không hiệu quả cho mảng lớn.
Độ phức tạp:
Thời gian: O(n²) (duyệt tất cả dãy con).
Không gian: O(n) (lưu mảng tiền tố).
Ứng dụng thực tế
Tài chính: Tìm khoảng thời gian có lợi nhuận cao nhất trong chuỗi dữ liệu tài chính (ví dụ: giá cổ phiếu).
Xử lý tín hiệu: Xác định đoạn tín hiệu có tổng năng lượng lớn nhất.
Phân tích dữ liệu: Tìm dãy con tối ưu trong các bài toán liên quan đến tổng hoặc giá trị liên tiếp.
Phỏng vấn kỹ thuật: Kiểm tra khả năng tư duy thuật toán động và tối ưu hóa thời gian.