c# solution beats 90%


  • 0
    M
    public class Solution {
    public IList<int> LargestDivisibleSubset(int[] nums) {
        if(nums.Length == 0) return new List<int>();
        var list = new LinkedList<int>();
       
        Array.Sort(nums);
        var depths = new int[nums.Length];
        int maxDepth = 0, maxI = 0;
        
        for(int i = 1; i < nums.Length; i++) {
            var max = -1;
            for(int j = 0; j < i; j++) {
                if(nums[i] % nums[j] == 0)
                    max = Math.Max(max, depths[j]);
            }
            depths[i] = ++max;
            if(max > maxDepth) {
                maxDepth = max;
                maxI = i;
            }
        }
        
        list.AddFirst(nums[maxI]);
        for(int i = maxI - 1; i > -1; i--) {
            if(nums[maxI] % nums[i] != 0 || depths[i] + 1 != maxDepth)
                continue;
                
            list.AddFirst(nums[i]);
            maxDepth--;
            maxI = i;
        }
        return list.ToList();
    }
    

    }


Log in to reply
 

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