Bài toán mảng con lớn nhất

Trong khoa học máy tính, bài toán tìm mảng con lớn nhất là bài toán tìm một mảng con liên tục của một mảng một chiều chứa cả số dương và số âm sao cho mảng con này có tổng các phần tử là lớn nhất. Ví dụ: mảng −2, 1, −3, 4, −1, 2, 1, −5, 4 có mảng con lớn nhất là 4, −1, 2, 1 với tổng là 6.

Thuật toán Kadane

Thuật toán Kadane quét qua các phần tử của mảng, tính tại từng vị trí tổng lớn nhất có thể của các mảng con kết thúc tại vị trí đó. Mảng con này có thể rỗng khi tổng của các phần tử bằng 0 hoặc có thể chứa nhiều hơn một phần tử so với mảng con lớn nhất tại vị trí trước đó.

Thuật toán của chương trình được viết bằng ngôn ngữ Python.

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Thuật toán này tính toán dựa trên cấu trúc con tối ưu (mảng con lớn nhất tại một vị trí được tính toán đơn giản từ các bài toán con nhỏ hơn là mảng con lớn nhất tại vị trí trước đó) nên thuật toán này thuộc dạng bài toán quy hoạch động.

Tổng quát hóa

Bài toán này có thể được tổng quát hóa lên các mảng nhiều chiều hơn. Tuy nhiên khi đó việc giải bài toán sẽ phức tạp hơn.

Tham khảo