My java solution beats 98.29% with dp and binarysearch.


  • 0

    At first I used dp,the solution beats only 19.So I try to optimize it.

    public static List<Integer> largestDivisibleSubset(int[] nums) {
    		List<Integer> list = new ArrayList<>();
    		if (nums.length == 0)
    			return list;
    		Arrays.sort(nums);
    		int[][] record = new int[2][nums.length];// index count
    		Arrays.fill(record[0], -1);
    		for (int i = 0; i < nums.length; i++) {
    			int maxIndex = i;
    			int max = 0;
    			int t = 0;
    			t = Arrays.binarySearch(nums, 0, i, nums[i] / 2);//binarysearch ,this is important
    			t = t < 0 ? -t - 1 : t;
    			for (int j = t; j >= 0; j--) {
    				if (nums[i] % nums[j] == 0 && record[1][j] > max) {
    					maxIndex = j;
    					max = record[1][j];
    				}
    			}
    			record[0][i] = max == 0 ? -1 : maxIndex;
    			record[1][i] = max + 1;
    		}
    		int max = 0;
    		for (int i = 0; i < record[0].length; i++)
    			max = record[1][i] > record[1][max] ? i : max;
    		list.add(nums[max]);
    		while (record[0][max] != -1) {
    			list.add(nums[record[0][max]]);
    			max = record[0][max];
    		}
    		Collections.sort(list);
    		return list;
    	}
    

Log in to reply
 

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