JavaScript DP O(n^2) with Explanation


  • 0

    Basic idea:

    1. sort nums
    2. use DP to find the largest subset size for each number
      • record the biggest subset size and index of the last number in this subset
      • record the index of previous number in the subset
    3. traverse from back to front, start from the last number in the largest subset, continuously add previous number to the subset until there is no previous index

    For example:

    nums:    [1, 2, 4, 8]
    dp:      [1, 2, 3, 4]
    pre:    [-1, 0, 1, 2]
    
    maxSize = 4, maxIndex = 3
    
    start from maxIndex,
    add 8 (index: 3, pre index: 2)
    add 4 (index: 2, pre index: 1)
    add 2 (index: 1, pre index: 0)
    add 1 (index: 0, pre index: -1)
    
    /**
     * @param {number[]} nums
     * @return {number[]}
     */
    var largestDivisibleSubset = function(nums) {
        if (nums.length < 1) {
            return []
        }
        
        nums.sort(function (a, b) { return a-b })
        let dp = new Array(nums.length).fill(0)
        let pre = new Array(nums.length).fill(-1)
        let max = 0
        let maxIndex = 0
        dp[0] = 1
        
        for (let i = 1; i < nums.length; i++) {
            for (let j = i-1; j >=0 ; j--) {
                if (nums[i] % nums[j] === 0) {
                    if (dp[i] < dp[j]+1) {
                        dp[i] = dp[j]+1
                        pre[i] = j
                        if (dp[i] > max) {
                            max = dp[i]
                            maxIndex = i
                        }
                    }
                }
            }
        }
        
        let subset = []
        let p = maxIndex
        while(p !== -1) {
            subset.unshift(nums[p])
            p = pre[p]
        }
        
        return subset
    };
    

Log in to reply
 

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