Java DP solution, beats 100% submissions


  • 0
    T
    List<List<List<Integer>>> dp = new ArrayList<List<List<Integer>>>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> output = new ArrayList<List<Integer>>();
        if(nums.length == 0){
            return output;
        }
        //handle the first element in DP (Owing to ascending order, we should inverse the order of nums.
        List<List<Integer>> tempF = new ArrayList<List<Integer>>();
        List<Integer> arrF = new ArrayList<Integer>();
        arrF.add(nums[nums.length-1]);
        tempF.add(arrF);
        dp.add(tempF);
        for (int i = nums.length-2; i >= 0; i--){
            List<List<Integer>> temp = new ArrayList<List<Integer>>();
            List<Integer> arr = new ArrayList<Integer>();
            arr.add(nums[i]);
            temp.add(arr);
            for(int j = i+1; j < nums.length; j++){
                //make sure that every list is in ascending order
                if(nums[j] < nums[i]){
                    continue;
                }
                else{
                    for(List<Integer> k : dp.get(nums.length-1-j)){
                        List<Integer> tempList = new ArrayList<Integer>();
                        tempList.add(nums[i]);
                        for(int z : k)
                            tempList.add(z);
                        temp.add(tempList);
                    }
                }
            }
        }
        for(List<List<Integer>> i : dp){
            for(List<Integer> j : i){
                if(j.size()!=1){
                    output.add(j);
                }
            }
        }
        HashSet h = new HashSet(output);
        output.clear();
        output.addAll(h);
        dp.add(output);
        return output;
    }

Log in to reply
 

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