[LeetCode] 368. Largest Divisible Subset

 Problem : https://leetcode.com/problems/largest-divisible-subset/

For a valid subset in ascending order [A, B, C, D], if the largest number D can be divided by the Number e, then the subset [A, B, C, D, e] is still a valid subset.

Time Complexity = O ( N ** 2)

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        N = len(nums)
        
        # edge cases when nums is empty or singleton list
        if N <= 1: return nums
        
        # sort the input nums first to form an ascending list
        nums.sort()
        
        # dp[i] : valid subset ends by i-th num
        # dp[i][0] = predecessor of i-th num
        # dp[i][1] = max length of the valid subset ends by i-th num
        dp = [[-1,0] for _ in range(N)]
        
        subsetLen = 0
        subsetEnd = 0
        
        for i in range(N):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[i][1] < dp[j][1] + 1:
                        dp[i][1] = dp[j][1] + 1
                        dp[i][0] = j
                    
                        if dp[i][1] > subsetLen:
                            subsetEnd = i
                            subsetLen = dp[i][1]
        
        result = []
        
        # iterate back to gather all elements of the valid subset
        while subsetEnd != -1:
            result.append(nums[subsetEnd])
            subsetEnd = dp[subsetEnd][0]
        
        return result[::-1]