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.

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

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.

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.

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

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;}

Matlab, O ( n 2 ⁿ ), 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

Python, O (2 ⁿ ), 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