Đề bài: Dãy con có tổng dài nhất

Cho dãy số nguyên ~a_1, a_2, \dots, a_n~. Hãy tìm dãy con liên tiếp (subarray) có tổng lớn nhất.

Yêu cầu:

• Dãy con phải liên tiếp (định nghĩa dãy con)
• Có thể chọn dãy con chỉ gồm ~1~ phần tử

Ký hiệu tổng dãy con từ ~l~ đến ~r~ là: ~S(l,r) = a_l + a_{l+1} + \dots + a_r~.

Thuật toán "trâu"/"ngây thơ" (Thuần Brute-force)

Ý tưởng

• Xét mọi cặp ~l, r~ với ~1 \le l \le r \le n~, tính tổng dãy con ~[l, r]~, lấy giá trị lớn nhất.

Công thức

• ~\displaystyle S(l,r) = \sum_{i=l}^{r} a_i~.

Độ phức tạp thời gian

• Có ~\mathcal{O}(n^2)~ cặp ~l, r~:
  • Mỗi lần tính tổng mất ~\mathcal{O}(n)~.
• Tổng: ~\mathcal{O}(n^3)~.

Nhận xét

• Cài đặt đơn giản.
• Tuy vậy chạy quá chậm, chỉ chạy được với ~n~ rất nhỏ.

Thuật toán “trâu” tối ưu (Brute-force nhưng tối ưu hơn)

Ý tưởng

• Vẫn duyệt mọi cặp ~l, r~, nhưng tối ưu cách tính tổng:
  • Cố định ~l~.
  • Sau đó mở rộng ~r~ dần và cộng dồn.

Mô tả

• Với mỗi ~l~:
  • Khởi tạo ~\text{sum} = 0~.
  • Với ~r~ từ ~l~ đến ~n~: ~\text{sum += } a_r~.
  • Cập nhật kết quả.

Độ phức tạp thời gian

• Hai vòng lặp ~l, r~:
  • Mỗi phép cộng ~\mathcal{O}(1)~.
• Tổng: ~\mathcal{O}(n^2)~.

Nhận xét

• Nhanh hơn rất nhiều so với thuật toán ngây thơ.
• Vẫn chưa đủ tốt nếu ~n~ lớn ~(10^5)~.

Quy hoạch động Kadane (Kadane's Dynamic Programming)

Ý tưởng

• Xét bài toán con:
  • Gọi ~dp[i]~ là tổng lớn nhất của dãy con kết thúc tại vị trí ~i~.
  • Tại ~i~, ta có hai lựa chọn:
    • Bắt đầu dãy con mới tại ~i~.
    • Nối ~a_i~ vào dãy con tốt nhất kết thúc tại ~i-1~.
• Công thức truy hồi: ~\text{dp}[i] = \max(a_i, \text{dp}[i-1] + a_i)~.
• Kết quả cuối cùng: ~\text{ans} = \displaystyle \max_{1 \le i \le n} \text{dp}[i]~.

Độ phức tạp thời gian và không gian

1. Thời gian: ~\mathcal{O}(n)~.
2. Bộ nhớ: ~\mathcal{O}(n)~ (có thể tối ưu xuống ~\mathcal{O}(1)~).

Nhận xét

• Hiệu quả, nhanh đét.

Tổng tiền tố (Prefix Sum)

Ý tưởng

• Ta cần tối đa hóa: ~\max(S(l, r)) = \max (\text{pref}[r] - \text{pref}[l - 1])~.
• Với mỗi ~r~, muốn giá trị này lớn nhất thì ~\text{pref}[l - 1]~ phải nhỏ nhất trước đó.

Cài đặt

• Duyệt ~r~ từ ~1~ đến ~n~.
• Luôn lưu ~\text{minPref}~ là giá trị nhỏ nhất của ~\text{pref}~ đã gặp.
• Cập nhật: ~\text{ans} = \max(\text{ans}, \text{pref}[r] - \text{minPref})~.

Độ phức tạp thời gian và không gian

• Thời gian: ~\mathcal{O}(n)~.
• Bộ nhớ: ~\mathcal{O}(n)~ (hoặc ~\mathcal{O}(1)~ nếu tối ưu).

Nhận xét

• Bản chất tương đương Kadane.