Java O(N^2) Brute Force - Forward and Backward Scan


  • -1

    Replace previous DP method with Brute Force. O(N^2) time and O(N) spaces.

    1. Forward Scan
    2. Backward Scan
    
    
        public List<Integer> largestDivisibleSubset(int[] nums) {
          List<Integer> maxSeq = new LinkedList<>();
          if (nums == null) return maxSeq;
          int n = nums.length;
          if (n == 0) return maxSeq;
        
          Arrays.sort(nums);
          for (int i = n - 1; i >= 0; i--) {
            LinkedList<Integer> currList = new LinkedList<>();
            currList.add(nums[i]);
            for (int j = i - 1; j >= 0; j--) {
              if (currList.getFirst() % nums[j] == 0) {
                currList.addFirst(nums[j]);
              }
            }
        
            if (currList.size() > maxSeq.size()) {
              maxSeq = currList;
            }
          }
        
          return maxSeq;
        }
        
        public List<Integer> largestDivisibleSubset(int[] nums) {
          List<Integer> maxSeq = new ArrayList<>();
          if (nums == null) return maxSeq;
          int n = nums.length;
          if (n == 0) return maxSeq;
        
          Arrays.sort(nums);
          for (int i = n - 1; i >= 0; i--) {
            List<Integer> currList = new ArrayList<>();
            currList.add(nums[i]);
            for (int j = i - 1; j >= 0; j--) {
              if (currList.get(0) % nums[j] == 0) {
                currList.add(0, nums[j]);
              }
            }
        
            if (currList.size() > maxSeq.size()) {
              maxSeq = currList;
            }
          }
          
          return maxSeq;
        }

  • 0
    S

    @coolguy wrong answer for "[1,2,4,8,9,72]"


Log in to reply
 

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