Cho 1 mảng số nguyên không trùng lặp, hãy tìm mảng con lớn nhất sao cho với mỗi Si và Sj thỏa mãn điều kiện Si chia hết cho Sj hoặc Sj chia hết cho Si. Nếu có nhiều mảng con cùng kích thước có thể lựa chọn tùy ý 1 đáp án.
Sử dụng Dynamic Programing trong bài này.
Bước 1: Sort mảng đầu vào theo thứ tự tăng dần
Bước 2: Giả sử ta có mảng count với count[i] là số lượng phần tử trong mảng con từ index 0 -> i, init giá trị mảng này với giá trị 1 vì luôn tồn tại mảng con chứa 1 phần tử thỏa mãn yêu cầu. Để tính giá trị của count[i] ta duyệt j từ 0 đến i - 1 nếu nums[i] chia hết cho nums[j] ta sẽ lưu lại giá trị lớn nhất của nums[j] + 1.
Bước 3: Tìm giá trị lớn nhất của mảng count, giá trị này chính là số lượng phần tử lớn nhất của mảng
Buớc 4: Duyệt mảng count từ last index về 0, dựa trên max để init mảng con.
Bước 1: Sort mảng đầu vào theo thứ tự tăng dần
Bước 2: Giả sử ta có mảng count với count[i] là số lượng phần tử trong mảng con từ index 0 -> i, init giá trị mảng này với giá trị 1 vì luôn tồn tại mảng con chứa 1 phần tử thỏa mãn yêu cầu. Để tính giá trị của count[i] ta duyệt j từ 0 đến i - 1 nếu nums[i] chia hết cho nums[j] ta sẽ lưu lại giá trị lớn nhất của nums[j] + 1.
Bước 3: Tìm giá trị lớn nhất của mảng count, giá trị này chính là số lượng phần tử lớn nhất của mảng
Buớc 4: Duyệt mảng count từ last index về 0, dựa trên max để init mảng con.