Làm cách nào rút gọn số vòng lặp của bài này

c++

(Ron Einstein) #1

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 ạ


(rogp10) #3

Gợi ý :smiley:

  • 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.


(Ron Einstein) #4

có thể cụ thể hơn một chút được không anh


(rogp10) #5

Thao tác swap chỉ thay đổi vị trí trong mảng :smiley: 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.


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?