Una subsecuencia es una secuencia que puede derivarse de otra secuencia eliminando algunos elementos sin cambiar el orden de los elementos restantes. Una subsecuencia estrictamente creciente es una subsecuencia en la cual cada elemento es más grande que el precedente.
La subsecuencia creciente más pesada de una secuencia es la subsecuencia estrictamente creciente que tiene la mayor suma de elementos.
Implemente un programa o función en su idioma de elección que encuentre la suma de elementos de la subsecuencia creciente más pesada de una lista dada de enteros no negativos.
Ejemplos:
[] -> 0 ([])
[3] -> 3 ([3])
[3, 2, 1] -> 3 ([3])
[3, 2, 5, 6] -> 14 ([3, 5, 6])
[9, 3, 2, 1, 4] -> 9 ([9])
[3, 4, 1, 4, 1] -> 7 ([3, 4])
[9, 1, 2, 3, 4] -> 10 ([1, 2, 3, 4])
[1, 2, 4, 3, 4] -> 10 ([1, 2, 3, 4])
[9, 1, 2, 3, 4, 5, 10] -> 25 ([1, 2, 3, 4, 5, 10])
[3, 2, 1, 2, 3] -> 6 ([1, 2, 3])
Tenga en cuenta que solo tiene que dar al elemento la suma de la subsecuencia creciente más pesada, no la subsecuencia misma.
El código asintóticamente más rápido gana, con un tamaño de código más pequeño en bytes como un desempate.
Respuestas:
javascript (ES6)
O(n log n)
253 caracteresesto usa árboles de fenwick (un árbol de fenwick máximo) para encontrar máximos de ciertas subsecuencias.
Básicamente, en la matriz subyacente del tipo de datos, cada lugar se corresponde con un elemento de la lista de entrada, en el mismo orden. el árbol fenwick se inicializa con 0 en todas partes.
del más pequeño al más grande, tomamos un elemento de la lista de entrada y buscamos el máximo de los elementos a la izquierda. son los elementos que pueden estar antes de este en la subsecuencia, porque están a la izquierda en la secuencia de entrada, y son más pequeños, porque ingresaron al árbol antes.
así que el máximo que encontramos es la secuencia más pesada que puede llegar a este elemento, por lo que agregamos a esto el peso de este elemento y lo establecemos en el árbol.
entonces, simplemente devolvemos el máximo del árbol completo es el resultado
probado en firefox
fuente
Python, O (n log n)
No jugué golf, porque estoy compitiendo principalmente en el lado del código más rápido de las cosas. Mi solución es la
heaviest_subseq
función, y también se incluye un arnés de prueba en la parte inferior.Análisis de tiempo de ejecución:
Cada elemento tiene su posición de inserción buscada una vez, se inserta una vez y posiblemente se elimina una vez, además de un número constante de búsquedas de valor por ciclo. Como estoy usando el paquete bisect incorporado y el paquete blist , cada una de esas operaciones son
O(log n)
. Por lo tanto, el tiempo de ejecución general esO(n log n)
.El programa funciona manteniendo una lista ordenada de las mejores subsecuencias crecientes posibles, representadas como una tupla de valor final y suma de secuencia. Una subsecuencia creciente está en esa lista si no se han encontrado otras subsecuencias hasta ahora cuyo valor final sea menor y la suma sea al menos igual de grande. Estos se mantienen en orden creciente de valor final, y necesariamente también en orden creciente de suma. Esta propiedad se mantiene comprobando el sucesor de cada subsecuencia recién encontrada, y eliminándola si su suma no es lo suficientemente grande, y repitiendo hasta que se alcanza una subsecuencia con una suma mayor, o se alcanza el final de la lista.
fuente
Python, O (n log n)
Utilicé una transformación de índice y una ingeniosa estructura de datos (árbol indexado binario) para trivializar el problema.
El árbol indexado binario puede realizar dos operaciones en log (n): aumentar un valor en el índice i y obtener el valor máximo en [0, i). Inicializamos cada valor en el árbol a 0. Indexamos el árbol usando el rango de elementos, no su índice. Esto significa que si indexamos el árbol en el índice i, todos los elementos [0, i) son los elementos más pequeños que el que tiene rango i. Esto significa que obtenemos el máximo de [0, i), le agregamos el valor actual y lo actualizamos en i. El único problema es que esto incluirá valores que son menores que el valor actual, pero vendrán más adelante en la secuencia. Pero dado que nos movemos a través de la secuencia de izquierda a derecha e inicializamos todos los valores en el árbol a 0, estos tendrán un valor de 0 y, por lo tanto, no afectarán el máximo.
fuente
Python 2 -
O(n^2)
- 114 bytesfuente
C ++ -
O(n log n)
- 261 bytesDebería arreglarse ahora:
fuente
auto S=set<pair<I,I>>();
es más largo que simplementeset<pair<I,I>> S;
.#define I int
es más largo queusing I=int;
. No hay necesidad de asignarn
a cualquier cosa, se puede reemplazarauto n=*prev(S.lower_bound({w,-1}));I y=n.second
conI y=prev(S.lower_bound({w,-1}))->second+w;
.S
es muy complicada, puede renunciar a la inserción y usarstd::set<std::pair<int,int>>S{{-1,0}};
.using namespace std;using I=int;I h(vector<I>l){I W=0;set<pair<I,I>>S{{-1,0}};for(I w:l){I y=prev(S.lower_bound({w,-1}))->second+w;W=max(W,y);S.insert({w,y});}return W;}
std::max
, usoW=y>W?y:W;
.Matlab, O ( n 2 n ), 90 bytes
Ejemplos:
fuente
Python, O (2 n ), 91 bytes
Esto es más por diversión que por ser competitivo. Una solución recursiva arcana:
fuente
max(m,l[0])
dado quenot(l[0]<m)
es justol[0]
, ¿seguro?