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.
Respostas:
javascript (ES6)
O(n log n)
253 caracteresisso 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
fonte
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_subseq
função, e um chicote de teste também está incluído na parte inferior.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.
fonte
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.
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.
fonte
Python 2 -
O(n^2)
- 114 bytesfonte
C ++ -
O(n log n)
- 261 bytesDeve ser corrigido agora:
fonte
auto S=set<pair<I,I>>();
é mais do que simplesmenteset<pair<I,I>> S;
.#define I int
é maior queusing I=int;
. Não há necessidade de atribuirn
a nada, você pode substituirauto n=*prev(S.lower_bound({w,-1}));I y=n.second
porI y=prev(S.lower_bound({w,-1}))->second+w;
.S
é muito complicada, você pode simplesmente abandonar a inserção e o usostd::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
, useW=y>W?y:W;
.Matlab, O ( n 2 n ), 90 bytes
Exemplos:
fonte
Python, O (2 n ), 91 bytes
Isso é mais divertido do que ser competitivo. Uma solução recursiva arcana:
fonte
max(m,l[0])
dado quenot(l[0]<m)
é justol[0]
, com certeza?