Sous-séquence la plus longue ayant des valeurs de coin supérieures

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

Étant donné un tableau arr[] contenant une permutation aléatoire du premier N nombres naturels, la tâche consiste à trouver la plus longue sous-séquence ayant la propriété que le premier et le dernier éléments sont supérieurs à tous les autres éléments de la sous-séquence.
Exemples:

Saisir: arr[] = {3, 1, 5, 2, 4}
Production: 4
La sous-séquence est {3, 1, 2, 4}. Les éléments d’angle de cette sous-séquence sont supérieurs à tous les autres éléments.
Saisir: arr[] = {1, 2, 3, 4, 5}
Production: 2
On ne peut pas faire une sous-suite de taille supérieure à 2.

Approcher: Si nous fixons les éléments les plus à gauche et les plus à droite d’une sous-séquence, nous sommes intéressés à compter combien d’éléments entre eux ont une valeur plus petite que les deux. Une implémentation simple de cette idée a une complexité de O (N3).
Afin de réduire la complexité, nous abordons le problème différemment. Au lieu de fixer les extrémités de la sous-séquence, nous fixons les éléments intermédiaires. L’idée est que pour un X donné (1 ≤ X ≤ N), on veut trouver deux éléments supérieurs ou égaux à X, qui ont entre eux autant d’éléments que possible inférieurs à X. Pour un X fixe, il est optimal de choisir le les éléments les plus à gauche et les plus à droite ≤ X. Nous avons maintenant un meilleur O(N2) la solution.
Lorsque X augmente, l’élément le plus à gauche ne peut qu’augmenter, tandis que celui le plus à droite ne peut que diminuer. On peut utiliser un pointeur pour chacun d’eux pour obtenir une complexité amortie de O(N).
Voici la mise en œuvre de l’approche ci-dessus :

C++

#include<bits/stdc++.h>

using namespace std;

#define MAXN 100005

int longestSubSeq(int n, int arr [])

{

    int max_length = 0;

    

    

    int pos[MAXN];

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

        pos[arr[i] - 1] = i;

    int left = n, right = 0;

    for (int i = n - 1, num = 1; i >= 0;

                       i -= 1, num += 1)

    {

        

        

        left = min(left, pos[i]);

        

        

        right = max(right, pos[i]);

        

        max_length = max(max_length,

                         right - left - num + 3);

    }

    

    

    if (n == 1)

        max_length = 1;

    return max_length;

}

int main()

{

    int arr[] = { 1, 2, 3, 4, 5 };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << longestSubSeq(n, arr);

}

Java

class GFG {

    static int MAXN = (int)1e5 + 5;

    

    

    static int longestSubSeq(int n, int[] arr)

    {

        int max_length = 0;

        

        

        int[] pos = new int[MAXN];

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

            pos[arr[i] - 1] = i;

        int left = n, right = 0;

        for (int i = n - 1, num = 1; i >= 0;

                         i -= 1, num += 1) {

            

            

            left = Math.min(left, pos[i]);

            

            

            right = Math.max(right, pos[i]);

            

            max_length = Math.max(max_length,

                      right - left - num + 3);

        }

        

        

        if (n == 1)

            max_length = 1;

        return max_length;

    }

    

    public static void main(String[] args)

    {

        int arr[] = { 1, 2, 3, 4, 5 };

        int n = arr.length;

        System.out.println(longestSubSeq(n, arr));

    }

}

Python3

MAXN = 100005

def longestSubSeq(n, arr):

    max_length = 0

    

    

    pos = [0] * MAXN

    for i in range (0, n):

        pos[arr[i] - 1] = i

    left = n

    right = 0

    num = 1

    

    for i in range (n - 1, -1, -1) :

        

        

        left = min(left, pos[i])

        

        

        right = max(right, pos[i])

        

        max_length = max(max_length,

                right - left - num + 3)

    

        num = num + 1

        

    

    

    if (n == 1) :

        max_length = 1

    return max_length

arr = [ 1, 2, 3, 4, 5 ]

n = len(arr)

print(longestSubSeq(n, arr))

C#

using System;

class GFG

{

    static int MAXN = (int)1e5 + 5;

    

    

    static int longestSubSeq(int n, int[] arr)

    {

        int max_length = 0;

        

        

        int[] pos = new int[MAXN];

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

            pos[arr[i] - 1] = i;

        int left = n, right = 0;

        for (int i = n - 1, num = 1; i >= 0;

                        i -= 1, num += 1)

        {

            

            

            left = Math.Min(left, pos[i]);

            

            

            right = Math.Max(right, pos[i]);

            

            max_length = Math.Max(max_length,

                    right - left - num + 3);

        }

        

        

        if (n == 1)

            max_length = 1;

        return max_length;

    }

    

    public static void Main()

    {

        int []arr = { 1, 2, 3, 4, 5 };

        int n = arr.Length;

        Console.WriteLine(longestSubSeq(n, arr));

    }

}

PHP

<?php

$MAXN = 100005;

function longestSubSeq($n, $arr)

{

    global $MAXN;

    $max_length = 0;

    

    

    $pos = array();

    for ($i = 0; $i < $n; $i++)

        $pos[$arr[$i] - 1]= $i;

    $left = $n;

    $right = 0;

    $num = 1;

    for ($i = $n - 1; $i >= 0 ; $i--, $num++)

    {

        

        

        

        $left = min($left, $pos[$i]);

        

        

        $right = max($right, $pos[$i]);

        

        $max_length = max($max_length,

                          $right - $left - $num + 3);

    }

    

    

    

    if ($n == 1)

        $max_length = 1;

    return $max_length;

}

$arr = array(1, 2, 3, 4, 5);

$n = sizeof($arr);

echo longestSubSeq($n, $arr);

?>

Javascript

<script>

    

    

    let MAXN = 1e5 + 5;

  

    

    

    function longestSubSeq(n, arr)

    {

        let max_length = 0;

  

        

        

        let pos = new Array(MAXN);

        pos.fill(0);

  

        for (let i = 0; i < n; i++)

            pos[arr[i] - 1] = i;

  

        let left = n, right = 0;

  

        for (let i = n - 1, num = 1; i >= 0;

                        i -= 1, num += 1)

        {

  

            

            

            left = Math.min(left, pos[i]);

  

            

            

            right = Math.max(right, pos[i]);

  

            

            max_length = Math.max(max_length,

                    right - left - num + 3);

        }

  

        

        

        if (n == 1)

            max_length = 1;

  

        return max_length;

    }

    

    let arr = [ 1, 2, 3, 4, 5 ];

    let n = arr.length;

    document.write(longestSubSeq(n, arr));

    

</script>

Laisser un commentaire

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