Ta có thể giải bài toán này trong \(O(N)\) bằng Thuật toán Kadane (Quy hoạch động):

• Gọi curr_max là tổng đoạn con lớn nhất kết thúc tại vị trí hiện tại.
• Gọi max_so_far là tổng đoạn con lớn nhất tìm được trong toàn bộ mảng.
• Khi đi qua phần tử \(A_i\), ta quyết định: hoặc kéo dài đoạn con trước đó (curr_max + A_i), hoặc bắt đầu một đoạn con mới từ chính \(A_i\).
• Công thức truy hồi: curr_max = max(A_i, curr_max + A_i).
• Sau mỗi bước, cập nhật: max_so_far = max(max_so_far, curr_max).

Độ phức tạp thời gian là \(O(N)\) và độ phức tạp bộ nhớ là \(O(1)\).