My O(n^3) java solution using dynamic programming


  • 0
    D
    public class Solution {
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<Map<List<Integer>, Integer>> lists=new ArrayList<>();
            List<List<Integer>> res=new ArrayList<>();
            for(int len=2; len<=nums.length; len++){
                lists.add(new HashMap<List<Integer>, Integer>());
                for(int i=0; i<=nums.length-len; i++){
                    if(len==2){
                        for(int j=i+1; j<nums.length; j++){
                            if(nums[i]<=nums[j]){
                                List<Integer> list=new ArrayList<>();
                                list.add(nums[i]);
                                list.add(nums[j]);
                                if(!lists.get(0).containsKey(list)){
                                    lists.get(0).put(list, i);
                                }
                                else{
                                    lists.get(0).put(list, Math.max(i, lists.get(0).get(list)));
                                }
                                
                            }
                        }
                    }
                    else{
                        for(List<Integer> list: lists.get(len-3).keySet()){
                            if(nums[i]<=nums[lists.get(len-3).get(list)] && i<lists.get(len-3).get(list)){
                                List<Integer> t=new ArrayList<>(list);
                                t.add(0,nums[i]);
                                if(!lists.get(len-2).containsKey(t)){
                                    lists.get(len-2).put(t,i);
                                }
                                else{
                                    lists.get(len-2).put(t, Math.max(i, lists.get(len-2).get(t)));
                                }
                            }
                        }
                    }
                }
            }
            
            for(Map<List<Integer>, Integer> map: lists){
                for(List<Integer> list: map.keySet()){
                    res.add(list);
                }
            }
            
            return res;
            
        }
    }
    

Log in to reply
 

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