My Java Dp Solution


  • 0
    B
     public List<Integer> largestDivisibleSubset(int[] nums) {
          List<Integer> res = new ArrayList<>();
    		if (nums.length==0) {
    			return res;
    		}
    		if (nums.length==1) {
    			res.add(nums[0]);
    			return res;
    		}
    		int []dp = new int [nums.length];
    		Arrays.sort(nums);
    		List<List<Integer>> dpList = new ArrayList<>(nums.length);
    		for(int tmp:nums){
    			List<Integer> list = new ArrayList<>();
    			list.add(tmp);
    			dpList.add(list);
    		}
    		for(int i=0;i<nums.length;i++){
    			int len = dpList.get(i).size();
    			for(int j=i+1;j<nums.length;j++){
    				int tmp = nums[j]%nums[i];
    				if (tmp==0&&(len+1)>(dpList.get(j).size())) {
    					List<Integer> list = new ArrayList<>(dpList.get(i));
    					list.add(nums[j]);
    					dpList.set(j, list);
    				}
    			}
    		}
    		res = dpList.get(0);
    		for(List<Integer> list:dpList){
    			if (res.size()<list.size()) {
    				res = list;
    			}
    		}
    		return res;
    }
    

Log in to reply
 

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