Longueur de la plus longue sous-séquence croissante dans une chaîne

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Donné un chaîne de caractères Sil s’agit de trouver la longueur de sous-séquence croissante la plus longue présent dans la chaîne donnée.

Suite de caractères placés dans l’ordre croissant de leur Valeurs ASCII est appelée une suite croissante.

Exemples:

Saisir: S = “abcfgffs”
Production: 6
Explication: Sous-séquence “abcfgs” est la plus longue sous-séquence croissante présente dans la chaîne. Par conséquent, la longueur de la plus longue sous-séquence croissante est 6.

Saisir: S = “aaabac”
Production: 3

Approcher: L’idée est d’utiliser Programmation dynamique. Suivez les étapes ci-dessous pour résoudre le problème :

  • Initialiser un tableau, disons dp[] de taille 26à stocker à chaque jee index, la longueur de la plus longue sous-séquence croissante ayant (‘a’ + je)e caractère comme dernier caractère de la sous-séquence.
  • Initialiser la variable, par exemple lispour stocker la longueur de la sous-séquence requise.
  • Itérer sur chaque caractère de la chaîne S.
    • Pour chaque caractère rencontré, c’est-à-dire S[i] – ‘un’vérifiez tous les caractères, dites javec des valeurs ASCII inférieures à celles du caractère actuel.
    • Initialiser une variable, disons courantpour stocker la longueur de LIS se terminant par le caractère actuel.
    • Mise à jour courant avec max(curr, dp[j]).
    • Mettre à jour la longueur du LIS, par exemple lis, avec max(lis, curr + 1).
    • Mise à jour dp[S[i] – ‘un’] avec un maximum de ré[S[i] – ‘un’] et courant.
  • Enfin, imprimez la valeur de lis comme la longueur requise de LIS.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

int lisOtimised(string s)

{

    

    

    

    int dp[30] = { 0 };

    

    int N = s.size();

    

    int lis = INT_MIN;

    

    

    for (int i = 0; i < N; i++) {

        

        

        int val = s[i] - 'a';

        

        

        int curr = 0;

        

        

        for (int j = 0; j < val; j++) {

            curr = max(curr, dp[j]);

        }

        

        curr++;

        

        

        lis = max(lis, curr);

        

        dp[val] = max(dp[val], curr);

    }

    

    return lis;

}

int main()

{

    string s = "fdryutiaghfse";

    cout << lisOtimised(s);

    return 0;

}

Java

import java.util.*;

class GFG{

    

static int mn = -2147483648;

  

static int lisOtimised(String s)

{

    

    

    

    

    int []dp = new int[30];

    Arrays.fill(dp, 0);

    

    int N = s.length();

    

    int lis = mn;

    

    

    for(int i = 0; i < N; i++)

    {

        

        

        

        int val =  (int)s.charAt(i) - 97;

        

        

        int curr = 0;

        

        

        for(int j = 0; j < val; j++)

        {

            curr = Math.max(curr, dp[j]);

        }

        

        curr++;

        

        

        lis = Math.max(lis, curr);

        

        dp[val] = Math.max(dp[val], curr);

    }

    

    return lis;

}

public static void main(String[] args)

{

    String s = "fdryutiaghfse";

    

    System.out.print(lisOtimised(s));

}

}

Python3

def lisOtimised(s):

  

    

    

    

    dp = [0]*30

    

    N = len(s)

    

    lis = -10**9

    

    

    for i in range(N):

        

        

        val = ord(s[i]) - ord('a')

        

        

        curr = 0

        

        

        for j in range(val):

            curr = max(curr, dp[j])

        

        curr += 1

        

        

        lis = max(lis, curr)

        

        dp[val] = max(dp[val], curr)

    

    return lis

if __name__ == '__main__':

    s = "fdryutiaghfse"

    print (lisOtimised(s))

C#

using System;

using System.Collections.Generic;

class GFG

{

 static int mn = -2147483648;

  

 

static int lisOtimised(string s)

{

  

    

    

    

    int []dp = new int[30];

    Array.Clear(dp, 0, 30);

    

    int N = s.Length;

    

    int lis = mn;

    

    

    for (int i = 0; i < N; i++) {

        

        

        int val =  (int)s[i] - 97;

        

        

        int curr = 0;

        

        

        for (int j = 0; j < val; j++) {

            curr = Math.Max(curr, dp[j]);

        }

        

        curr++;

        

        

        lis = Math.Max(lis, curr);

        

        dp[val] = Math.Max(dp[val], curr);

    }

    

    return lis;

}

public static void Main()

{

    string s = "fdryutiaghfse";

    Console.Write(lisOtimised(s));

}

}

Javascript

<script>

function lisOtimised( s)

{

    

    

    

    let dp = new Array(30).fill(0);

    

    let N = s.length;

    

    

    let lis = Number.MIN_VALUE;

    

    

    for (let i = 0; i < N; i++) {

        

        

        let val = s.charCodeAt(i) - 'a'.charCodeAt(0);

        

        

        let curr = 0;

        

        

        for (let j = 0; j < val; j++) {

            curr = Math.max(curr, dp[j]);

        }

        

        curr++;

        

        

        lis = Math.max(lis, curr);

        

        dp[val] = Math.max(dp[val], curr);

    }

    

    return lis;

}

 let s = "fdryutiaghfse";

 document.write(lisOtimised(s));

</script>

Complexité temporelle : SUR)
Espace Auxiliaire : O(1)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *