当前位置：网站首页>9. lt.491 Longest increasing subsequence

9. lt.491 Longest increasing subsequence

2022-06-09 12:02:00 【Caicai's big data development path】

lt.491. Increasing subsequence

[ Case needs ]

Insert picture description here

[ Thought analysis ]

Insert picture description here

[ Code implementation ]

class Solution {
    
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> path = new  ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
    
        backTracking(nums, 0);

        return lists;
    }

    public void backTracking(int[] nums, int startIndex){
    
        //2.  The end condition , path There are more than two elements in 
        if(path.size() > 1){
    
            lists.add(new ArrayList<>(path));
            //return;
        }

        //3.  Single layer recursive logic 
        // How to remove the weight of each layer ?
        // for The process of looping is the process of traversing each layer ,  Every time you go back into for A loop is a walk through each layer 
        //  So we 
        int[] used = new int[201];
        for(int i = startIndex; i < nums.length; i++){
    
            // Carry out weight removal on the same layer 
            //  Two criteria ,
            //1.  Ascending operation ,  If path Number that already exists in  >  The one to be traversed nums[i],  Then skip this number 
            //2.  Each layer shall be de weighted ,  such as  [4,7] and [4,7] Although not on the same path ,  But on the same floor ,  Need to be heavy 
            if(!path.isEmpty() && nums[i] < path.get(path.size() - 1) || 
                    used[nums[i] + 100] == 1) continue;
      
            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}