old_contents: # Time:  O(n^2)
  # Space: O(n)
  
  # Given a set of distinct positive integers,
  # find the largest subset such that every pair (Si, Sj) of
  # elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
  #
  # If there are multiple solutions, return any subset is fine.
  #
  # Example 1:
  #
  # nums: [1,2,3]
  #
  # Result: [1,2] (of course, [1,3] will also be ok)
  # Example 2:
  #
  # nums: [1,2,4,8]
  #
  # Result: [1,2,4,8]
  
  class Solution(object):
      def largestDivisibleSubset(self, nums):
          """
          :type nums: List[int]
          :rtype: List[int]
          """
          if not nums:
              return []
  
          nums.sort()
          dp = [1] * len(nums)
          prev = [-1] * len(nums)
          largest_idx = 0
          for i in xrange(len(nums)):
              for j in xrange(i):
                  if nums[i] % nums[j] == 0:
                      if dp[i] < dp[j] + 1:
                          dp[i] = dp[j] + 1
                          prev[i] = j
                      if dp[largest_idx] < dp[i]:
                          largest_idx = i
          result = []
          i = largest_idx
          while i != -1:
              result.append(nums[i])
              i = prev[i]
          return result[::-1]
  
new_contents: # Time:  O(n^2)
  # Space: O(n)
  
  # Given a set of distinct positive integers,
  # find the largest subset such that every pair (Si, Sj) of
  # elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
  #
  # If there are multiple solutions, return any subset is fine.
  #
  # Example 1:
  #
  # nums: [1,2,3]
  #
  # Result: [1,2] (of course, [1,3] will also be ok)
  # Example 2:
  #
  # nums: [1,2,4,8]
  #
  # Result: [1,2,4,8]
  
  class Solution(object):
      def largestDivisibleSubset(self, nums):
          """
          :type nums: List[int]
          :rtype: List[int]
          """
          if not nums:
              return []
  
          nums.sort()
          dp = [1] * len(nums)
          prev = [-1] * len(nums)
          largest_idx = 0
          for i in xrange(len(nums)):
              for j in xrange(i):
                  if nums[i] % nums[j] == 0:
                      if dp[i] < dp[j] + 1:
                          dp[i] = dp[j] + 1
                          prev[i] = j
              if dp[largest_idx] < dp[i]:
                  largest_idx = i
          result = []
          i = largest_idx
          while i != -1:
              result.append(nums[i])
              i = prev[i]
          return result[::-1]
  
subject: Update largest-divisible-subset.py