Największy wzrost podsekwencji

9

Podsekwencja to sekwencja, którą można uzyskać z innej sekwencji poprzez usunięcie niektórych elementów bez zmiany kolejności pozostałych elementów. Ściśle rosnąca podsekwencja to podsekwencja, w której każdy element jest większy niż poprzedni.

Najsilniej rosnącym podsekwencją sekwencji jest ściśle rosnąca podsekwencja, która ma największą sumę elementów.

Zaimplementuj program lub funkcję w wybranym języku, który znajdzie sumę pierwiastków o największej rosnącej podsekwencji danej listy liczb całkowitych nieujemnych.

Przykłady:

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

Zauważ, że musisz podać sumę pierwiastków o największej narastającej podsekwencji, a nie samą podsekwencję.


Wygrywa asymptotycznie najszybszy kod, z mniejszym rozmiarem kodu w bajtach jako rozstrzygającym.

orlp
źródło
Jak zamierzasz radzić sobie z nieporównywalnymi asymptotykami? Istnieją potencjalnie dwie ważne zmienne: długość sekwencji i rozmiar największego elementu w sekwencji.
Peter Taylor
@PeterTaylor Wybieram długość sekwencji jako asymptotyczną. Twoje rozwiązanie nie może zakładać żadnego ograniczenia na liczbach całkowitych, w szczególności nie może zapętlać ani alokować pamięci na podstawie wielkości zaangażowanych liczb. Wybaczono ci, jeśli wybór języka ograniczył liczby całkowite, ale nie możesz wykorzystać tego faktu w swoim rozwiązaniu. Czy to spełnia twoje obawy?
orlp
Częściowo. Nadal teoretycznie możliwe (choć prawdopodobnie mało prawdopodobne) jest, że fakt, że porównanie dwóch niepowiązanych liczb całkowitych przyjmuje wielkość proporcjonalną do ich logu, może mieć znaczenie. Możesz zezwolić na podstawowe operacje (dodawanie, porównanie, może mnożenie) na liczbach całkowitych, aby założyć, że jest to czas O (1).
Peter Taylor,
@PeterTaylor Czy transdhothotomiczny model obliczeń jest wystarczająco specyficzny?
orlp
Wydaje się rozsądne.
Peter Taylor

Odpowiedzi:

3

javascript (ES6) O(n log n)253 znaków

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}

wykorzystuje to drzewa fenwick (maksymalne drzewo fenwick), aby znaleźć maksima niektórych podsekwencji.

w zasadzie w podstawowej tablicy typu danych każde miejsce jest dopasowane do elementu z listy danych wejściowych, w tej samej kolejności. drzewo fenwick jest inicjowane z 0 wszędzie.

od najmniejszego do największego bierzemy element z listy danych wejściowych i szukamy maksymalnej liczby elementów po lewej stronie. są to elementy, które mogą znajdować się przed tym w podsekwencji, ponieważ znajdują się po lewej stronie sekwencji wejściowej i są mniejsze, ponieważ wcześniej weszły do ​​drzewa.

więc maksimum, które znaleźliśmy, jest najcięższą sekwencją, która może dostać się do tego elementu, więc dodajemy do tego wagę tego elementu i ustawiamy go w drzewie.

wtedy po prostu zwracamy maksimum całego drzewa.

testowane na Firefox

dumny haskeller
źródło
4

Python, O (n log n)

Nie grałem w golfa, ponieważ rywalizuję przede wszystkim o najszybszą stronę kodową. Moim rozwiązaniem jest heaviest_subseqfunkcja, a na dole znajduje się również uprząż testowa.

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

Analiza środowiska wykonawczego:

Każdy element ma raz sprawdzoną pozycję wstawiania, jest wstawiany raz i prawdopodobnie jest usuwany jeden raz, oprócz stałej liczby wyszukiwań wartości na pętlę. Ponieważ używam wbudowanego pakietu bisect i pakietu blist , każda z tych operacji jest O(log n). Zatem całkowity czas działania wynosi O(n log n).

Program działa poprzez utrzymywanie posortowanej listy najlepszych możliwych rosnących podciągów, reprezentowanych jako krotka wartości końcowej i sumy sekwencji. Rosnąca podsekwencja znajduje się na tej liście, jeśli nie znaleziono do tej pory innych podsekwencji, których wartość końcowa jest mniejsza, a suma jest co najmniej tak duża. Są one utrzymywane w porządku rosnącym według wartości końcowej, a niekoniecznie także w porządku rosnącym sumy. Właściwość ta jest utrzymywana przez sprawdzanie następcy każdego nowo znalezionego podsekwencji i usuwanie go, jeśli jego suma nie jest wystarczająco duża, i powtarzanie do momentu osiągnięcia podsekwencji z większą sumą lub osiągnięcia końca listy.

isaacg
źródło
Interesujące, zupełnie inne rozwiązanie niż moje .
orlp
2

Python, O (n log n)

Użyłem transformacji indeksu i sprytnej struktury danych (binarne drzewo indeksowane), aby trywializować problem.

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

Binarne drzewo indeksowane może wykonywać dwie operacje w log (n): zwiększyć wartość w indeksie i uzyskać maksymalną wartość w [0, i). Inicjujemy każdą wartość w drzewie do 0. Indeksujemy drzewo za pomocą rankingu elementów, a nie ich indeksu. Oznacza to, że jeśli indeksujemy drzewo o indeksie i, wszystkie elementy [0, i) są elementami mniejszymi niż ten o randze i. Oznacza to, że otrzymujemy maksimum z [0, i), dodajemy do niego bieżącą wartość i aktualizujemy w i. Jedynym problemem jest to, że obejmie to wartości, które są mniejsze niż bieżąca wartość, ale pojawią się później w sekwencji. Ale ponieważ przechodzimy przez sekwencję od lewej do prawej i inicjalizujemy wszystkie wartości w drzewie do 0, będą one miały wartość 0, a zatem nie wpłyną na maksimum.

orlp
źródło
1

Python 2 - O(n^2)- 114 bajtów

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
źródło
1

C ++ - O(n log n)- 261 bajtów

Należy teraz naprawić:

#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
źródło
auto S=set<pair<I,I>>();jest dłuższy niż po prostu set<pair<I,I>> S;. #define I intjest dłuższy niż using I=int;. Nie ma potrzeby, aby przypisać ndo niczego, można zastąpić auto n=*prev(S.lower_bound({w,-1}));I y=n.secondz I y=prev(S.lower_bound({w,-1}))->second+w;.
orlp
Aha, a inicjalizacja Sjest bardzo skomplikowana, możesz po prostu zrezygnować z wkładki i używać std::set<std::pair<int,int>>S{{-1,0}};.
orlp
@orlp dzięki! Pokazuje, że nie używam c ++;)
Tyilo
Oto znacznie krótsza wersja (wciąż wymaga zestawu i wektora to):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
No i rzuć std::max, użyj W=y>W?y:W;.
orlp
0

Matlab, O ( n 2 n ), 90 bajtów

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

Przykłady:

>> f([])
ans =
     0
>> f([3])
ans =
     3
>> f([3, 2, 5, 6])
ans =
    14
Luis Mendo
źródło
0

Python, O (2 n ), 91 bajtów

To więcej dla zabawy niż rywalizacji. Tajemne rekurencyjne rozwiązanie:

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
źródło
1
max(m,l[0])biorąc pod uwagę, że not(l[0]<m)jest to na l[0]pewno?
Peter Taylor,
@PeterTaylor Derp.
orlp
Ta odpowiedź nie wydaje się poważnym argumentem.
pppery