30 ngày chống COVID cùng Leetcode | Ngày 03

Khi đọc đề bài này, tôi đã khá buồn, đây là một bài toán tôi không làm tốt trong kỳ thi HSG Tỉnh, khiến cho đứa ngồi bên cạnh tôi về Nhất. Nghĩ trong cuộc đời này  đã trượt khá nhiều cơ hội, khi nó tìm đến, đã không có chuẩn bị kỹ càng để đón nhận nó.

Dù tôi chỉ kém người đứng đầu một chút điểm, nhưng Nhất thì chỉ có một thôi còn Nhì thì có thể nhiều, điều đó làm tôi buồn một thời gian chỉ vì một lỗi ngớ ngẩn này.

Đề bài khá tương tự thế này, tất nhiên với một đề thi thật thì họ sẽ biến đổi, viết văn chương thành một vấn đề thật, nhưng cốt lõi vấn đề giống như đề bài ở đây:

Đây là một bài toán kinh điển trong được giải bằng cách Quy hoạch động, ý tưởng của phương pháp là, chia một bài toán lớn thành các bài toán nhỏ hơn đã có lời giải, nghe thì rất giống phương pháp chia để trị, chỉ khác là các bài toán nhỏ hơn của phương pháp Quy hoạch động sẽ phải lưu lại tất cả, để tìm lại về sau.

Để tìm Local_Maximum, giả dụ bằng cách nào đó ta đã biết Local_Maximum từ đoan [0,4] = 3;

Nhìn vào sơ đồ, ta có thể thấy Local_Maximum từ đoạn [0,5] sẽ không phải tính lại từ đầu, mà sẽ bằng đoạn [0,4] + arr[5];

Từ cách trên, ta có công thức truy hồi, thuật toán Kanade:

   Local_Maximum[i] = max(arr[i], Local_Maximum[i-1] +arr[i]);

 Thuật toán Kanade có độ phức tạp O(n) thời gian và O(n) không gian.

Trên đây là code implement bằng Java, còn đây là trang web tham khảo hình ảnh.