Largest Divisible Subset | Longest Increasing Subsequence (DP-44)

1. Why Do We Need This? (Problem Statement & Status Quo)

When exploring advanced dynamic programming patterns, we often encounter variations of the Longest Increasing Subsequence (LIS). While standard LIS problems focus strictly on maintaining strictly increasing numerical values across indices, real-world problems often impose different relational constraints between elements.

The Largest Divisible Subset problem asks us to find the largest possible subset from a given array of distinct numbers such that every pair of numbers within that subset satisfies a specific divisibility condition.

• The Challenge: Unlike standard subsets where order doesn't matter and any combination can be picked, a divisible subset requires every pair $(A[i], A[j])$ to be divisible by one another.
• The Pitfall: Brute-force generation of all possible subsets results in exponential time complexity ($O(2^n)$), which is intractable for large arrays. We need an optimal substructure and overlapping subproblems property.

2. Core Mental Model & Definitions

To understand the problem correctly, we must define the two core components: Subset and Divisibility.

Understanding Subsets vs. Subsequences

• Subsequence: Elements must appear in the same relative order as they occur in the original array (e.g., picking indices 0, 3, and 5).
• Subset: Elements can be picked in any order or configuration, and relative original indexing is not strictly enforced.

The Divisibility Rule

For any chosen subset of numbers, if we pick any two elements $A[i]$ and $A[j]$, the condition must hold:

Real-Life Analogy: Imagine arranging a hierarchical chain of nested boxes or Russian nesting dolls, where each outer box must be a clean multiple in size of the inner box it contains, ensuring smooth containment all the way down.

3. The Sorting Insight & Transitive Divisibility

At first glance, checking all pairs in an unsorted array seems complex because divisibility can go in either direction. However, a brilliant structural property emerges if we sort the array in ascending order first.

Why Sorting Changes Everything

Suppose we sort our array in ascending order: [1, 4, 8, 16]

If we pick elements sequentially such that each subsequent element is divisible by the previous element:

• $16 \pmod 8 == 0$ (16 is divisible by 8)
• $8 \pmod 4 == 0$ (8 is divisible by 4)
• $4 \pmod 1 == 0$ (4 is divisible by 1)

Because the array is sorted, transitive divisibility is automatically guaranteed! If $16$ is divisible by $8$, and $8$ is divisible by $4$, and $4$ is divisible by $1$, then $16$ is guaranteed to be divisible by $4$ and $1$ as well. We do not need to check every single pair against every other pair; we only need to check each element against its immediate predecessor in our chain.

4. Transforming LIS into LDS (Largest Divisible Subset)

Because sorting allows us to establish a linear chain of divisibility, this problem morphs directly into a variation of the Longest Increasing Subsequence (LIS) pattern.

Instead of checking whether Array[j] < Array[i] (as we did in LIS), we check whether Array[i] % Array[j] == 0.

Algorithmic Comparison

5. Step-by-Step Evolution of the Code

Below is the evolution from the standard LIS template to the specialized Largest Divisible Subset implementation.

Naive / Unsorted Approach (Flawed)

Trying to check divisibility without sorting requires quadratic/cubic checks for all possible pairings without a guaranteed linear chain.

Optimized Production Code (C++)

By sorting the array first, applying the modulo check, and maintaining a backtracking hash array, we achieve an optimal solution.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& arr) {
        int n = arr.size();
        if (n == 0) return {};

        // Step 1: Sort the array to enforce transitive divisibility
        sort(arr.begin(), arr.end());

        // Step 2: Initialize DP vector and Hash/Parent tracking vector
        vector<int> dp(n, 1);
        vector<int> hash(n);
        
        int maxLen = 1;
        int lastIndex = 0;

        for (int i = 0; i < n; i++) {
            hash[i] = i; // Initialize parent pointer to self
            for (int j = 0; j < i; j++) {
                // Check divisibility condition on sorted elements
                if (arr[i] % arr[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    hash[i] = j;
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                lastIndex = i;
            }
        }

        // Step 3: Backtrack using the hash array to reconstruct the subset
        vector<int> temp;
        temp.push_back(arr[lastIndex]);
        
        while (hash[lastIndex] != lastIndex) {
            lastIndex = hash[lastIndex];
            temp.push_back(arr[lastIndex]);
        }

        // The result can be returned in any order, but reversing gives a clean sorted sequence
        reverse(temp.begin(), temp.end());
        return temp;
    }
};

6. Complete Flow Walkthrough

Let's trace the execution flow for the input array: [1, 16, 7, 8, 4]

7. Complexity Analysis

• Time Complexity:

  • Sorting: $O(N \log N)$ where $N$ is the number of elements in the array.
  • DP Nested Loops: $O(N^2)$ for evaluating all pairs $(i, j)$.
  • Backtracking: $O(N)$ in the worst case to traverse the hash pointers.
  • Overall Time Complexity: $O(N^2 + N \log N) \approx O(N^2)$.

• Space Complexity:

  • $O(N)$ for the dp tracking vector.
  • $O(N)$ for the hash parent pointer vector.
  • $O(N)$ for the resulting subset storage vector.
  • Overall Space Complexity: $O(N)$.

8. Summary and Key Takeaways

• Problem Rebranding: The Largest Divisible Subset problem is fundamentally a disguised variation of the Longest Increasing Subsequence (LIS) pattern.
• The Power of Sorting: Sorting the array beforehand is the crucial mental unlock; it transforms an arbitrary divisibility check into a structured, transitive chain.
• Transitive Property: If $A$ divides $B$ and $B$ divides $C$, sorting guarantees $A$ automatically divides $C$, simplifying pairwise validation.
• Modulo Operator: Replace the strict greater-than comparison (arr[i] > arr[j]) from LIS with the divisibility condition (arr[i] % arr[j] == 0).
• Path Reconstruction: Use a hash (or parent) tracking array alongside the DP array to easily backtrack and reconstruct the exact subset elements.
• Order Flexibility: Since the problem allows returning any valid subset, sorting the output vector at the end provides a neat, readable ascending result.
• Efficiency: Achieving an $O(N^2)$ time and $O(N)$ space solution makes this approach highly scalable for standard constraint limits.