Em có một bài là tìm tổng ba số lớn nhất trong một mảng cho trước chia hết cho ba !
Nếu làm bình thường thì mình làm 3 vòng for lồng nhau còn nếu muốn rút gọn số vòng lặp còn 1 hay 2 thì phải làm sao ạ
Làm cách nào rút gọn số vòng lặp của bài này
Gợi ý 
- Chia mảng thành 3 phần gồm 3 dạng số 3k, 3k+1 và 3k+2 (k nguyên) (dùng trick O(1) mem).
- Lấy max mỗi phần.
O(n) time.
3 Likes
có thể cụ thể hơn một chút được không anh
Thao tác swap chỉ thay đổi vị trí trong mảng nên khéo dùng nó ta có thể chia mảng thành ba đoạn có tính chất riêng, nghĩa là một phần tử chỉ có thể nằm trong duy nhất một đoạn. Quicksort chia 3 (3-way) là ví dụ điển hình.
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?