Subsecuencia creciente más larga en Python

Aprenderemos qué es una subsecuencia y cómo calcular la subsecuencia creciente más larga de una matriz utilizando el enfoque de n cuadrados y el enfoque de búsqueda binaria en Python.

Use el enfoque N-cuadrado para calcular la subsecuencia creciente más larga en Python

Se hace una pregunta famosa sobre la subsecuencia de mayor crecimiento en la comunidad de Python y se hace en diferentes entrevistas. Es un problema de Leetcode, y la pregunta dice: se da una matriz no ordenada de enteros y se encuentra la longitud de la subsecuencia o subconjunto creciente más largo de la matriz dada.

Un subconjunto es como una matriz corta de una matriz; cada matriz podría tener múltiples subconjuntos. La otra cosa es que el subarreglo serían algunos de los elementos de este arreglo [10,9,2,5,3,7,101,18] pero en una subsecuencia continua.

Puede ser como [2, 3, 5, 7], pero no puede ser [2,3,101], por lo que no es necesario romper la secuencia cuando se habla de un subarreglo. Y, en consecuencia, el orden en que aparecen los elementos en el arreglo tiene que ser el mismo, pero puede ser cualquiera de los individuos.

Por ejemplo, en este caso, como vemos, la respuesta es [2, 3, 7,101]; el 5 no está ahí, pero está bien porque es una subsecuencia.

Si vemos la subsecuencia creciente más larga de [10,9,2,5,3,7,101,18], encontramos [2, 5, 7, 101]; esto también podría haber significado una respuesta, pero la respuesta también podría ser [2, 3, 7, 101] que también es nuestra otra subsecuencia. El [3, 7, 101] también es una subsecuencia, pero esa no es la más larga, por lo que no la consideraremos.

Puede haber más de una combinación; como acabamos de ver, solo necesitamos devolver la longitud.

Con el ejemplo, podríamos pensar fácilmente en una solución recursiva que comience con índices cero y recorra todos los caminos diferentes. Usando esta matriz [0,3,1,6,2,2,7], podríamos tomar, por ejemplo, con 0, podemos ir a 3, o podemos ir a 1 o ir a 6.

Y luego, a partir de ese momento, continúa recursivamente. Mira el siguiente ejemplo, qué camino es el más largo que va a ser exponencial; fácilmente podemos pensar que tiene que haber algún enfoque de programación dinámica.

Entonces, tenemos una matriz y cada uno de estos índices tiene al menos una longitud.

[0,3,1,6,2,2,7]
[1,1,1,1,1,1,1]

Comenzaremos en el primer índice, 0, cuya longitud es 1, pero con 3, podemos mirar hacia atrás y si 3 es más grande que 0, entonces 3 tiene longitudes 2 . Si vamos con 1 nuevamente, buscaremos detrás de todos los índices antes del índice actual.

A partir de los índices cero, podemos ver que 1 es mayor que 0, pero 1 no es mayor que 3, por lo que en este punto, estamos calculando 0 y 1, y su longitud sería 2.

[0,3,1,6,2,2,7]
[1,2,2,1,1,1,1]

Considerando 6, miremos atrás desde el principio, sabemos que 6 es mayor que [0,1] o [0,3], e incluyendo 6, su longitud sería 3 entonces también la longitud de 2 es 3, y así sucesivamente, este es un enfoque cuadrático.

[0,3,1,6,2,2,7]
[1,2,2,3,3,...]

Complejidad del tiempo y complejidad del espacio

Saltemos al código y creemos nuestra clase llamada CalculateSubSequence; dentro de la función lengthOfLIS, inicializamos nuestra variable nums_list para que tenga la longitud de nums con una matriz que será solo 1 vez.

Dentro de los bucles anidados, comprobaremos si el valor es mayor que el número que estamos comprobando. Luego, tomemos nuestra lista_nums de i, y actualizaremos el valor de lista_nums mientras tomamos el valor máximo usando lista_nums[i].

i viene después de iterar desde el bucle externo, y para nums_list[j], j viene después de iterar desde el bucle interno y luego agregamos 1 con él. Al final, devolvemos el valor máximo de nums_list.

class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:

        nums_list = [1] * len(nums)

        for i in range(len(nums) - 1, -1, -1):

            for j in range(i + 1, len(nums)):

                if nums[i] < nums[j]:

                    nums_list[i] = max(nums_list[i], nums_list[j] + 1)

        return max(nums_list)


sbs = CalculateSubSequence()
sbs.lengthOfLIS([0, 3, 1, 6, 2, 2, 7])

Aquí la complejidad temporal será n al cuadrado, y la complejidad espacial será o de n.

4

La solución anterior es suficiente, pero otro enfoque, n log, usa una búsqueda binaria en el lado izquierdo de nuestra matriz temporal usando bisect_left.

from bisect import bisect_left


class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        tmp = [nums[0]]
        for n in nums:
            x = bisect_left(tmp, n)
            if x == len(tmp):
                tmp.append(n)
            elif tmp[x] > n:
                tmp[x] = n
        return len(tmp)


sbs = CalculateSubSequence()
sbs.lengthOfLIS([0, 3, 1, 6, 2, 2, 7])

Producción :

4