Subseqüência crescente mais pesada

9

Uma subsequência é uma sequência que pode ser derivada de outra sequência, excluindo alguns elementos sem alterar a ordem dos elementos restantes. Uma subsequência estritamente crescente é uma subsequência na qual cada elemento é maior que o anterior.

A subsequência crescente mais pesada de uma sequência é a subsequência estritamente crescente que possui a maior soma de elementos.

Implemente um programa ou função no seu idioma de escolha que encontre a soma do elemento da subsequência crescente mais pesada de uma determinada lista de números inteiros não negativos.

Exemplos:

                    [] ->  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])

Observe que você só precisa fornecer ao elemento a soma da subsequência crescente mais pesada, não a subsequência em si.


O código assintoticamente mais rápido vence, com um tamanho de código menor em bytes como desempatador.

orlp
fonte
Como você planeja lidar com assintóticos incomparáveis? Há potencialmente duas variáveis ​​importantes: o comprimento da sequência e o tamanho do maior elemento da sequência.
Peter Taylor
@PeterTaylor Eu escolho o comprimento da sequência como assintótico. Sua solução não deve assumir nenhum limite para os números inteiros e, em particular, não faz loop ou aloca memória com base no tamanho dos números envolvidos. Você será perdoado se sua escolha de idioma tiver números inteiros limitados, mas você não deve usar esse fato em sua solução. Isso satisfaz suas preocupações?
orlp
Parcialmente. Ainda é teoricamente possível (embora provavelmente improvável) que o fato de que a comparação de dois números inteiros ilimitados tenha tamanho proporcional ao seu log possa ser relevante. Você pode permitir que operações básicas (adição, comparação, talvez multiplicação) nos números inteiros sejam consideradas como tempo O (1).
Peter Taylor
@PeterTaylor O modelo transdicotômico de computação é específico o suficiente?
orlp 01/08/2015
Parece razoável.
Peter Taylor

Respostas:

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}

isso usa árvores fenwick (uma árvore fenwick máxima) para encontrar o máximo de determinadas subsequências.

basicamente, na matriz subjacente do tipo de dados, cada local é correspondido com um elemento da lista de entrada, na mesma ordem. a árvore fenwick é inicializada com 0 em todos os lugares.

do menor ao maior, pegamos um elemento da lista de entrada e procuramos o máximo de elementos à esquerda. eles são os elementos que podem estar antes deste na subseqüência, porque estão à esquerda na sequência de entrada e são menores, porque entraram na árvore anteriormente.

então o máximo que encontramos é a sequência mais pesada que pode chegar a esse elemento e, portanto, adicionamos a isso o peso desse elemento e o definimos na árvore.

então, simplesmente retornamos o máximo de toda a árvore é o resultado.

testado no firefox

orgulhoso haskeller
fonte
4

Python, O (n log n)

Eu não joguei isso porque estou competindo principalmente no lado do código mais rápido. Minha solução é a heaviest_subseqfunção, e um chicote de teste também está incluído na 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álise de tempo de execução:

Cada elemento tem sua posição de inserção procurada uma vez, é inserida uma vez e é possivelmente excluída uma vez, além de um número constante de pesquisas de valor por loop. Como estou usando o pacote bisect interno e o pacote blist , cada uma dessas operações é O(log n). Assim, o tempo de execução geral é O(n log n).

O programa funciona mantendo uma lista classificada das melhores subsequências crescentes possíveis, representadas como uma tupla de valor final e soma de sequência. Uma subsequência crescente está nessa lista se não houver outras subsequências encontradas até agora cujo valor final seja menor e a soma seja pelo menos igual. Eles são mantidos em ordem crescente de valor final e necessariamente também em ordem crescente de soma. Essa propriedade é mantida verificando o sucessor de cada subsequência recém-encontrada e excluindo-a se sua soma não for grande o suficiente, e repetindo até que uma subsequência com uma soma maior seja atingida ou o final da lista seja atingido.

isaacg
fonte
Interessante, uma solução muito diferente da minha .
orlp
2

Python, O (n log n)

Usei uma transformação de índice e uma estrutura de dados bacana (árvore indexada binária) para banalizar o 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))

A árvore indexada binária pode executar duas operações no log (n): aumentar um valor no índice i e obter o valor máximo em [0, i). Inicializamos cada valor na árvore como 0. Indexamos a árvore usando a classificação dos elementos, não o índice. Isso significa que, se indexarmos a árvore no índice i, todos os elementos [0, i) serão menores que o da classificação i. Isso significa que obtemos o máximo de [0, i), adicionamos o valor atual a ele e atualizamos em i. O único problema é que isso incluirá valores inferiores ao valor atual, mas que serão apresentados posteriormente na sequência. Mas, como percorremos a sequência da esquerda para a direita e inicializamos todos os valores na árvore para 0, esses terão um valor de 0 e, portanto, não afetarão o máximo.

orlp
fonte
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
fonte
1

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

Deve ser corrigido agora:

#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
fonte
auto S=set<pair<I,I>>();é mais do que simplesmente set<pair<I,I>> S;. #define I inté maior que using I=int;. Não há necessidade de atribuir na nada, você pode substituir auto n=*prev(S.lower_bound({w,-1}));I y=n.secondpor I y=prev(S.lower_bound({w,-1}))->second+w;.
orlp
Ah, e a inicialização de Sé muito complicada, você pode simplesmente abandonar a inserção e o uso std::set<std::pair<int,int>>S{{-1,0}};.
orlp
@orlp thanks! Isso mostra que eu não uso c ++;)
Tyilo
Aqui está uma versão muito mais curta (ainda precisa do conjunto e vector incluem):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, e despejar o std::max, use 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

Exemplos:

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

Python, O (2 n ), 91 bytes

Isso é mais divertido do que ser competitivo. Uma solução 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
fonte
11
max(m,l[0])dado que not(l[0]<m)é justo l[0], com certeza?
Peter Taylor
@PeterTaylor Derp.
orlp
Esta resposta não parece ser um candidato sério.
pppery