Largest Divisible Subset | Leetcode 368

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        
        //Step-1: Sort the array and Find LIS length
        sort(nums.begin(),nums.end());
        int lis = 1;
        vector<int> dp(n+1,1);
        for(int i=1;i<n;++i){
            for(int j=0;j<i;++j){
                if(nums[i]%nums[j]==0 && 1+dp[j]>dp[i]){
                    dp[i] = 1+dp[j];
                    if(lis<dp[i])
                        lis = dp[i];
                }
            }
        }
        //Step-2: Find one possible LIS
        int prev = -1;
        for(int i=n-1;i>=0;i--){
            if(dp[i]==lis &&  (prev%nums[i]==0 || prev==-1)){
                ans.push_back(nums[i]);
                lis -=1;
                prev = nums[i];
            }
        }
        return ans;
    }
};
/*
//JAVA
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        
        // Step-1: Sort the array and Find LIS length
        Arrays.sort(nums);
        int lis = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0 && 1 + dp[j] > dp[i]) {
                    dp[i] = 1 + dp[j];
                    if (lis < dp[i]) {
                        lis = dp[i];
                    }
                }
            }
        }
        
        // Step-2: Find one possible LIS
        int prev = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == lis && (prev == -1 || prev % nums[i] == 0)) {
                ans.add(nums[i]);
                lis--;
                prev = nums[i];
            }
        }
        
        return ans;
    }
}

#Python
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = []
        
        # Step-1: Sort the array and Find LIS length
        nums.sort()
        lis = 1
        dp = [1] * n
        
        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and 1 + dp[j] > dp[i]:
                    dp[i] = 1 + dp[j]
                    if lis < dp[i]:
                        lis = dp[i]
        
        # Step-2: Find one possible LIS
        prev = -1
        for i in range(n - 1, -1, -1):
            if dp[i] == lis and (prev == -1 or prev % nums[i] == 0):
                ans.append(nums[i])
                lis -= 1
                prev = nums[i]
        
        return ans

*/