"Một lập trình viên liệu có cần biết thuật toán không?" "Học đại học công nghệ thông tin để làm gì? Có khác gì so với không học đại học mà đi code không?" "Môn cấu trúc và giải thuật học để làm gì? Môn này khó như vậy không học có code được không?" .... Có rất nhiều câu hỏi liên quan đến vấn đề này. Hầu hết những câu hỏi này đã từng hoặc ít nhất là các dev đều đã từng nghe thấy ở đâu đó rồi. Thì để trả lời cho các câu hởi này thì chỉ cần các bạn chịu khó search google tý là ra hàng nghìn kết quả nha =)), nên là mình không trả lời nữa.

Cơ mà cũng có ý kiến cho rằng thôi thời buổi hiện giờ máy móc phát triển sung lượng RAM tăng lên từng ngày á, thì cần gì phải tối tưu cho nó chạy nhanh làm chi, nhanh hơn có mấy mili giây,.... hazzz. Kể cũng đúng một anh đi trước mình cũng cứng chứ bộ, bảo: "dăm ba cái thuật toán, giờ mài chỉ cần có thêm xí tiền triển khai là ổn, giờ điện toán đám mây là thế mạnh rồi, có lởm đi chăng nữa thì thuê nhiều máy ảo là ngon ngay". Nghe có vẻ thuyết phục nhỉ =)) . Thế vậy giờ học để làm gì nữa.

Cú tát đến từ thực tế

Tình cờ mình có mày mò vọc vạch chút xíu về adruino, code chơi chơi. Ôi và nó "ngu bò" voãi. Code quen kiểu mặc kệ đời nhiều rồi code sang con này không quen. Tùy từng con cơ mà con mình đang dùng có bộ nhớ lưu trữ nhiều đến mức chỉ có 1 .......00 MB (100MB đó). Nạp code không cẩn thận quá luôn =)) khóc dòng dòng. Đấy là chưa kể ko biết built được hết đống code thì nó chạy có full RAM không (hồi xưa toàn vét cạn ao hồ thôi ). Thôi thì hận đời chửi nó ngu có 100MB. Cơ mà tại mình cả thôi. Nhìn chung code cái gì cũng nên có cấu trúc và giải thuật tối ưu.

Nào chúng ta cùng đến với những bài toán đầu tiên. let's start!

1. Bài toán

Mở đầu bài toán đã thấy rắc rối rồi à nha:

Bài toán tìm dãy con lớn nhất. Cho dãy số: a1, a2, a3, ...., an
Dãy số a(i), a(i+1), ..., a(j) với 1 <= i <= j <= n được gọi là dãy con của dãy đã cho.
Câu hỏi: hãy tìm trọng lượng lớn nhất của dãy con, tức là tìm cực đại (có thể gọi dãy con có trọng lượng lớn
nhất là dãy con lớn nhất).

Ví dụ: Nếu dãy đã cho là: -2, 11, -4, 13, -5, 2. Thì cần đưa ra câu trả lời là 20 (là trọng lượng của dãy con 11, -4, 13)

2. Phân tích bài toán

Nếu bạn là người mới học hoặc chưa tiếp xúc với thuật toán nhiều, có thể nghĩ tới một cách giải đơn giản (nhưng “hơi bị ngáo” 🤣):

Duyệt hết tất cả các dãy con có thể có, tính tổng, chọn cái nào lớn nhất.

Nghe ổn mà nhỉ? Có sao đâu?

Nhưng nếu bạn để ý, số lượng dãy con liên tiếp có thể được sinh ra từ dãy n phần tử là:

• Có n dãy con bắt đầu từ phần tử đầu tiên,

• n-1 dãy con bắt đầu từ phần tử thứ 2,

• ...

• Tổng cộng là n(n+1)/2 dãy con.

Rồi mỗi dãy con bạn lại phải tính tổng một lần nữa... => Độ phức tạp O(n³) nếu bạn làm ngây thơ.

Với n = 10^4 thì xác định là code bạn lên bảng thầy gọi xuống liền =))

3. Kadane – Người hùng thầm lặng 🦸

Rất may, bài toán này đã được người ta nghiên cứu và tìm ra một cách giải cực kỳ hiệu quả. Thuật toán này tên là Kadane’s Algorithm, và độ phức tạp của nó chỉ là O(n). Chính xác là đi một vòng duy nhất qua dãy và xử lý thôi.

Ý tưởng: Duyệt qua từng phần tử trong dãy từ trái sang phải.

Tại mỗi bước, ta giữ hai biến:

• max_current: Tổng lớn nhất kết thúc tại vị trí hiện tại.

• max_global: Tổng lớn nhất toàn cục từ đầu tới giờ.

Công thức:

max_current = max(a[i], max_current + a[i])
max_global = max(max_global, max_current)

Tức là:

• Tại vị trí i, nếu cộng thêm a[i] mà tổng lại nhỏ hơn chính a[i] thì ta bỏ luôn đoạn trước đó, bắt đầu lại từ đây.
• Cập nhật tổng lớn nhất toàn cục nếu tổng hiện tại lớn hơn.

4. Cài đặt Python ngắn gọn

def max_subarray(arr): max_current = max_global = arr[0] for num in arr[1:]: max_current = max(num, max_current + num) max_global = max(max_global, max_current) return max_global

Thử chạy:

arr = [-2, 11, -4, 13, -5, 2]
print(max_subarray(arr)) # Output: 20

5. Ứng dụng thực tế?

Xử lý tín hiệu cảm biến – Không phải lúc nào cũng phẳng lặng

Trong các hệ thống đo đạc cảm biến liên tục (ví dụ: đo độ rung, âm thanh, ánh sáng...), thường sẽ có một đoạn ngắn trong tín hiệu là quan trọng nhất – ví dụ rung mạnh nhất, tiếng ồn cao nhất,...

Ta cũng lại quay về bài toán: Tìm đoạn tín hiệu liên tục có giá trị tích cực (tổng) cao nhất.

Một con robot đang đo rung trên cầu chẳng hạn, nó cần biết "đoạn nào rung dữ nhất?" => Dùng Kadane.