Hướng dẫn giải của MAXRECT
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Ta xem xét hai loại hình chữ nhật: Loại hình chữ nhật chứa các ô màu vàng và loại hình chữ nhật chứa các ô màu xanh. Từ đó tìm được hình chữ nhật lớn nhất.
Nhận xét rằng trên cột thứ ~j~ sẽ có ~x_j=h_j~ ô màu vàng và ~y_j=m-h_j~ ô màu xanh.
Do vậy: Để tìm hình chữ nhật lớn nhất màu vàng ta quy về bài toán tìm dãy con ~y_i … y_j~ sao cho ~min(y_i,…,y_j )×(j-i+1)~ lớn nhất. Để tìm hình chữ nhật lớn nhất màu xanh thực hiện tương tự trên mảng ~ x_1,x_2,…,x_n~.
Kỹ thuật được sử dụng là dùng stack quản lý min.
Thời gian thực hiện thuật toán là ~o(n)~