C++ Tìm tập con cặp chia hết lớn nhất

Cho mảng phần tử phân biệt. Tìm tập con lớn nhất sao cho mọi cặp phần tử lớn chia hết phần tử nhỏ. Ví dụ:

Input: {10,5,3,15,20} → Output: 3 (tập con 10,5,20)
Input: {18,1,3,6,13,17} → Output: 4 (tập con 18,1,3,6)

Phương pháp giải

Sắp xếp mảng. dp[i] = kích thước tập con lớn nhất với phần tử nhỏ nhất là a[i]. Duyệt từ cuối về đầu: dp[i] = 1 + max(dp[j]) với j>i và a[j]%a[i]==0. Kết quả = max(dp[i]).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int largestSubsetPair(int* a, int n) {
    int dp[n];
    dp[n-1] = 1;
    int largest = 0;

    for (int i=n-2; i>=0; i--) {
        int maxi = 0;
        for (int j=i+1; j

Kết quả
4

Giải thích
DP từ cuối: với a[i] làm phần tử nhỏ nhất, tìm bội số a[j] đã tính dp[j]. dp[i] = 1 + max(dp[j]).

Kết luận
Đã giải bài toán tập con cặp chia hết lớn nhất bằng DP O(n²) sau khi sắp xếp. Code C++ áp dụng cho C, Java, Python. Hy vọng hữu ích.