Thuật toán ng dụng
Bài thực hành số 1.2: Cấu trúc dữ liệu
TS. Bùi Quốc Trung, TA. Đặng Xuân Vương
Trường Đại học Bách khoa Nội
Viện Công nghệ thông tin Truyền thông
Ngày 16 tháng 3 năm 2021
TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 1 / 21
Mục lục
1HIST
2REROAD
3SIGNAL
TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 2 / 21
Mục lục
1HIST
2REROAD
3SIGNAL
TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 3 / 21
02. HIST
Ncột với độ cao l1,l2, ... xếp liên tiếp.
Tìm diện tích hình chữ nhật lớn nhất nằm gọn trong Ncột.
TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 4 / 21
Thuật toán
Nhận xét: Hình chữ nhật 2 cột biên i,jsao cho i<j diện tích
(ji+1)×min(li, ..., lj).
Thuật toán: Thử hết các cặp (i,j), duyệt từ iđến jđể tìm cột thấp
nhất (tương tự bài SUBSEQMAX).
Độ phức tạp: O(n3).
TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 5 / 21