Programmation dynamique du LetCode Day, partie 10

300. Sous-séquence croissante la plus longue

Étant donné un tableau d'entiers nums, renvoie la longueur du plus long strictement croissante
sous-séquence
.

Exemple 1 :

Entrée : nums = [10,9,2,5,3,7,101,18]
Sortie : 4
Explication : La sous-séquence croissante la plus longue est [2,3,7,101], donc la longueur est 4.
Exemple 2 :

Entrée : nums = [0,1,0,3,2,3]
Sortie : 4
Exemple 3 :

Entrée : nums = [7,7,7,7,7,7,7]
Sortie : 1

Contraintes :

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Suivi : pouvez-vous proposer un algorithme qui s'exécute en complexité temporelle O(n log(n)) ?
Page originale

Mauvais code

    public int lengthOfLIS(int[] nums) {
        int start = nums[0];
        int pre = nums[0];
        int preMax = nums[0];
        int cnt = 1;
        int max = 1;

        for(int i=1; i<nums.length; i++){
            if(nums[i] < start){
                max = Math.max(max, cnt);
                start = nums[i];
                cnt = 1;
            } 
            else if(nums[i] > pre){
                cnt ++;
            }
            pre = nums[i];
            System.out.println("cur:"+nums[i] + " pre:"+pre+ " count:" + cnt);
        }
        return Math.max(max, cnt);
    }


</p>
<h2>
  
  
  Correction d'un bug
</h2>


<pre class="brush:php;toolbar:false">

Apprendre des autres

    public int lengthOfLIS(int[] nums) {


        TreeMap<Integer,Integer> map = new TreeMap<>();

        map.put(Integer.MIN_VALUE,0);

       for(int i: nums)
       {
           map.put(i,map.get(map.lowerKey(i))+1);
           while(map.higherKey(i)!=null && map.get(map.higherKey(i))<=map.get(i)) 
           {
            map.remove(map.higherKey(i));
           }
       }

       return map.get(map.lastKey());

    }

---

674. Sous-séquence croissante continue la plus longue

Étant donné un tableau non trié de nombres entiers, renvoie la longueur de la plus longue sous-séquence croissante continue (c'est-à-dire un sous-tableau). La sous-séquence doit être strictement croissante.

Une sous-séquence croissante continue est définie par deux indices l et r (l < r) tels qu'elle est [nums[l], nums[l + 1], ..., nums[r - 1], nums [r]] et pour chaque l <= i < r, nums[i] &Lt ; nums[i + 1].

Exemple 1 :

Entrée : nums = [1,3,5,4,7]
Sortie : 3
Explication : La sous-séquence croissante continue la plus longue est [1,3,5] de longueur 3.
Même si [1,3,5,7] est une sous-suite croissante, elle n'est pas continue car les éléments 5 et 7 sont séparés par élément
4.
Exemple 2 :

Entrée : nums = [2,2,2,2,2]
Sortie : 1
Explication : La sous-séquence croissante continue la plus longue est [2] de longueur 1. Notez qu'elle doit être strictement
en augmentation.

Contraintes :

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
Page originale

Algorithme gourmand

    public int findLengthOfLCIS(int[] nums) {
        if(nums.length < 1){
            return 0;
        }
        int res = 1;
        int cnt = 1;
        int pre = nums[0];
        for(int i=1; i<nums.length; i++){
            if(nums[i] > pre){
                cnt++;
            }else{
                res = Math.max(res, cnt);
                cnt = 1;
            }
            // System.out.println("cur: " + nums[i] + " pre:" + pre + " count:" + cnt);
            pre = nums[i];
        }
        return Math.max(res, cnt);
    }

Programmation dynamique

Contrairement à la question précédente, dans cette question, nous ne pouvons considérer que des sous-séquences croissantes en continu, ce qui simplifie le processus.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!