Editorial: Dãy con có tổng lớn nhất
đã đăng vào 24, Tháng 1, 2026, 10:22Note: ChatGPT Skibidi Ahead!!!!!!
Bài toán dãy con có tổng lớn nhất yêu cầu tìm một đoạn con liên tiếp trong dãy ~a_1, a_2, \dots, a_n~ sao cho tổng của nó là lớn nhất. Quá trình tiếp cận bài toán thường bắt đầu từ cách làm ngây thơ với việc thử mọi cặp chỉ số ~l, r~ và tính tổng trực tiếp, dẫn đến độ phức tạp ~\mathcal{O}(n^3)~. Sau đó, cách làm “trâu” cải tiến bằng việc cộng dồn khi cố định ~l~, giảm xuống ~\mathcal{O}(n^2)~. Từ đó, ta phát triển tư duy quy hoạch động với công thức ~\text{dp}[i] = \max(a_i, \text{dp}[i-1] + a_i)~, hay còn gọi là thuật toán Kadane, đạt hiệu quả ~\mathcal{O}(n)~. Một cách nhìn khác tương đương là sử dụng Prefix Sum ~\text{pref}[i]~ và tối ưu biểu thức ~\text{pref}[r] - \text{pref}[l-1]~ bằng cách duy trì giá trị nhỏ nhất trước đó. Cả hai phương pháp Dynamic Programming và Prefix Sum đều cho lời giải tối ưu và được sử dụng phổ biến trong thực tế.