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.
Odpowiedzi:
javascript (ES6)
O(n log n)
253 znakówwykorzystuje 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
źródło
Python, O (n log n)
Nie grałem w golfa, ponieważ rywalizuję przede wszystkim o najszybszą stronę kodową. Moim rozwiązaniem jest
heaviest_subseq
funkcja, a na dole znajduje się również uprząż testowa.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 wynosiO(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.
źródło
Python, O (n log n)
Użyłem transformacji indeksu i sprytnej struktury danych (binarne drzewo indeksowane), aby trywializować problem.
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.
źródło
Python 2 -
O(n^2)
- 114 bajtówźródło
C ++ -
O(n log n)
- 261 bajtówNależy teraz naprawić:
źródło
auto S=set<pair<I,I>>();
jest dłuższy niż po prostuset<pair<I,I>> S;
.#define I int
jest dłuższy niżusing I=int;
. Nie ma potrzeby, aby przypisaćn
do niczego, można zastąpićauto n=*prev(S.lower_bound({w,-1}));I y=n.second
zI y=prev(S.lower_bound({w,-1}))->second+w;
.S
jest bardzo skomplikowana, możesz po prostu zrezygnować z wkładki i używaćstd::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
, użyjW=y>W?y:W;
.Matlab, O ( n 2 n ), 90 bajtów
Przykłady:
źródło
Python, O (2 n ), 91 bajtów
To więcej dla zabawy niż rywalizacji. Tajemne rekurencyjne rozwiązanie:
źródło
max(m,l[0])
biorąc pod uwagę, żenot(l[0]<m)
jest to nal[0]
pewno?