Swift solution - Dynamic Programming


  • 0
    class Solution {
        func largestDivisibleSubset(_ nums: [Int]) -> [Int] {
            if nums.count < 2 {
                return nums
            }
            
            let nums = nums.sorted()
            var result = [Int]()
            var dp = [Int](repeatElement(0, count: nums.count))
            var maxIndex = 0
            var temp = 0
            var cur = 0
    
            for i in 1..<nums.count {
                for j in stride(from: i - 1, through: 0, by: -1) {
                    if nums[i] % nums[j] == 0 {
                        dp[i] = max(dp[i], dp[j] + 1)
                    }
                }
            }
            for i in 1..<nums.count {
                maxIndex = dp[i] > dp[maxIndex] ? i : maxIndex
            }
            temp = nums[maxIndex]
            cur = dp[maxIndex]
            for i in stride(from: maxIndex, through: 0, by: -1) {
                if temp % nums[i] == 0 && dp[i] == cur {
                    result.append(nums[i])
                    temp = nums[i]
                    cur -= 1
                }
            }
            
            return result
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.