Subsecuencia creciente más pesada

9

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.

orlp
fuente
¿Cómo planeas lidiar con asintóticas incomparables? Hay potencialmente dos variables importantes: la longitud de la secuencia y el tamaño del elemento más grande de la secuencia.
Peter Taylor
@PeterTaylor Elijo la longitud de la secuencia como asintótica. Su solución no debe asumir ningún límite en los enteros y, en particular, no hacer un bucle o asignar memoria en función del tamaño de los números involucrados. Se le perdona si su elección de idioma tiene enteros limitados, pero no debe hacer uso de este hecho en su solución. ¿Eso satisface tus preocupaciones?
orlp
Parcialmente. Todavía es teóricamente posible (aunque probablemente improbable) que el hecho de que la comparación de dos enteros ilimitados tome un tamaño proporcional a su registro podría ser relevante. Es posible que desee permitir operaciones básicas (suma, comparación, tal vez multiplicación) en los enteros para suponer que son O (1) tiempo.
Peter Taylor
@PeterTaylor ¿El modelo de cómputo transdicotómico es lo suficientemente específico?
orlp
Parece razonable.
Peter Taylor

Respuestas:

3

javascript (ES6) O(n log n)253 caracteres

function f(l){l=l.map((x,i)=>[x,i+1]).sort((a,b)=>a[0]-b[0]||1)
a=[0]
m=(x,y)=>x>a[y]?x:a[y]
for(t in l)a.push(0)
t|=0
for(j in l){for(i=(r=l[j])[1],x=0;i;i&=i-1)x=m(x,i)
x+=r[0]
for(i=r[1];i<t+2;i+=i&-i)a[i]=m(x,i)}for(i=t+1;i;i&=i-1)x=m(x,i)
return x}

esto 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

orgulloso Haskeller
fuente
4

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_subseqfunción, y también se incluye un arnés de prueba en la parte inferior.

import bisect
import blist

def heaviest_subseq(in_list):
    best_subseq = blist.blist([(0, 0)])
    for new_elem in in_list:

        insert_loc = bisect.bisect_left(best_subseq, (new_elem, 0))

        best_pred_subseq_val = best_subseq[insert_loc - 1][1]

        new_subseq_val = new_elem + best_pred_subseq_val

        list_len = len(best_subseq)
        num_deleted = 0

        while (num_deleted + insert_loc < list_len
               and best_subseq[insert_loc][1] <= new_subseq_val):
            del best_subseq[insert_loc]
            num_deleted += 1

        best_subseq.insert(insert_loc, (new_elem, new_subseq_val))

    return max(val for key, val in best_subseq)

tests = [eval(line) for line in """[]
[3]
[3, 2, 1]
[3, 2, 5, 6]
[9, 3, 2, 1, 4]
[3, 4, 1, 4, 1]
[9, 1, 2, 3, 4]
[1, 2, 4, 3, 4]
[9, 1, 2, 3, 4, 5, 10]
[3, 2, 1, 2, 3]""".split('\n')]

for test in tests:
    print(test, heaviest_subseq(test))

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 es O(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.

isaacg
fuente
Interesante, una solución muy diferente a la mía .
orlp
2

Python, O (n log n)

Utilicé una transformación de índice y una ingeniosa estructura de datos (árbol indexado binario) para trivializar el problema.

def setmax(a, i, v):
    while i < len(a):
        a[i] = max(a[i], v)
        i |= i + 1

def getmax(a, i):
    r = 0
    while i > 0:
        r = max(r, a[i-1])
        i &= i - 1
    return r

def his(l):
    maxbit = [0] * len(l)
    rank = [0] * len(l)
    for i, j in enumerate(sorted(range(len(l)), key=lambda i: l[i])):
        rank[j] = i

    for i, x in enumerate(l):
        r = rank[i]
        s = getmax(maxbit, r)
        setmax(maxbit, r, x + s)

    return getmax(maxbit, len(l))

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.

orlp
fuente
1

Python 2 - O(n^2)- 114 bytes

def h(l):
 w=0;e=[]
 for i in l:
    s=0
    for j,b in e:
     if i>j:s=max(s,b)
    e.append((i,s+i));w=max(w,s+i)
 return w
Tyilo
fuente
1

C ++ - O(n log n)- 261 bytes

Debería arreglarse ahora:

#include <set>
#include <vector>
int h(std::vector<int>l){int W=0,y;std::set<std::pair<int,int>>S{{-1,0}};for(w:l){auto a=S.lower_bound({w,-1}),b=a;y=prev(a)->second+w;for(;b!=S.end()&&b->second<=y;b++){}a!=b?S.erase(a,b):a;W=y>W?y:W;S.insert({w,y});}return W;}
Tyilo
fuente
auto S=set<pair<I,I>>();es más largo que simplemente set<pair<I,I>> S;. #define I intes más largo que using I=int;. No hay necesidad de asignar na cualquier cosa, se puede reemplazar auto n=*prev(S.lower_bound({w,-1}));I y=n.secondcon I y=prev(S.lower_bound({w,-1}))->second+w;.
orlp
Ah, y la inicialización de Ses muy complicada, puede renunciar a la inserción y usar std::set<std::pair<int,int>>S{{-1,0}};.
orlp
@orlp gracias! Muestra que no uso c ++;)
Tyilo
Aquí hay una versión mucho más corta (aún necesita el conjunto y el vector incluido):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;}
orlp
Ah, y tira el std::max, uso W=y>W?y:W;.
orlp
0

Matlab, O ( n 2 n ), 90 bytes

function m=f(x)
m=0;for k=dec2bin(1:2^numel(x)-1)'==49
m=max(m,all(diff(x(k))>0)*x*k);end

Ejemplos:

>> f([])
ans =
     0
>> f([3])
ans =
     3
>> f([3, 2, 5, 6])
ans =
    14
Luis Mendo
fuente
0

Python, O (2 n ), 91 bytes

Esto es más por diversión que por ser competitivo. Una solución recursiva arcana:

h=lambda l,m=0:l and(h(l[1:],m)if l[0]<=m else max(h(l[1:],m),l[0]+h(l[1:],l[0])))or 0
orlp
fuente
1
max(m,l[0])dado que not(l[0]<m)es justo l[0], ¿seguro?
Peter Taylor
@PeterTaylor Derp.
orlp
Esta respuesta no parece ser un contendiente serio.
pppery