Java dp solution: two arrays to store length and sequence


  • 0
    H

    Use two arrays for this dp solution
    Array dp will store the length of the largest subset
    Array prev will store the index of the element along the sequence
    dp need to fill 1 because the smallest subset will contain itself and have length of 1

     public List<Integer> largestDivisibleSubset(int[] nums) {
            
            List<Integer> ret = new ArrayList<Integer>();
            
            if (nums == null || nums.length == 0)
                return ret;
                
            Arrays.sort(nums);
            
            int[] dp = new int[nums.length];
            int[] prev = new int[nums.length];
            Arrays.fill(dp, 1);
            prev[0] = 0;
            
            for (int i = 1; i < nums.length; i++) {
                for (int j = i-1; j >= 0; j--) {
                    if (nums[i] % nums[j] == 0) {
                    
                        if (dp[j] + 1 > dp[i]) {
                            dp[i] = dp[j] + 1;
                            prev[i] = j;
                        }
                       
                    }
                }
            }
            
            // find the max of dp
            int maxIndex = 0;
            for (int i = 0; i < dp.length; i++) {
                if (dp[i] > dp[maxIndex]) {
                    maxIndex = i;
                }
            }
            
            int len = dp[maxIndex];
            
            while (true) {
                ret.add(nums[maxIndex]);
                maxIndex = prev[maxIndex];
                
                if (--len <= 0)
                    break;
            }
          
            return ret;
            
         
    
    
        }
    

Log in to reply
 

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