Chains and reconstruction (DP — Longest Increasing Subsequence Sub-pattern)

// Longest chain with a custom "j may come before i" rule, returned as the actual chain.
// Shown for divisibility (Largest Divisible Subset); sort first so the rule only looks back.
vector<int> longestChain(vector<int> a) {
    sort(a.begin(), a.end());
    int n = a.size(), end = 0;
    vector<int> dp(n, 1), parent(n, -1);
    auto canFollow = [&](int j, int i) { return a[i] % a[j] == 0; };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (canFollow(j, i) && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; parent[i] = j; }
        if (dp[i] > dp[end]) end = i;
    }
    vector<int> chain;
    for (int i = n ? end : -1; i != -1; i = parent[i]) chain.push_back(a[i]);   // walk back
    reverse(chain.begin(), chain.end());
    return chain;
}