Wyzwanie to polega od testu wstępnego na zamknięty kurs bezpieczeństwa cybernetycznego. W każdym razie nie ma to nic wspólnego z cyberbezpieczeństwem, służy jedynie przetestowaniu umiejętności logicznych i kodowania uczniów.
Zadanie
Napisz program, który usuwa wpisy z tablicy, dzięki czemu pozostałe wartości są sortowane w ściśle malejącej kolejności, a ich suma jest zmaksymalizowana spośród wszystkich innych możliwych sekwencji malejących.
Wejście i wyjście
Wejście będzie tablica wartości całkowitych bezwzględnie większy niż 0
i wszystkie różnią się między sobą . Możesz wybrać, czy chcesz czytać dane wejściowe z pliku, wiersza poleceń czy standardowego wejścia.
Wyjściowa będzie posortowana malejąca podgrupa wejściowa, której suma jest większa niż jakakolwiek inna możliwa pod-tablica posortowana malejąco.
Uwaga: [5, 4, 3, 2]
to subarray z [5, 4, 1, 3, 2]
, nawet jeśli 4
i 3
nie sąsiadują. Tylko dlatego, że 1
pękło.
Rozwiązanie Bruteforce
Najprostszym rozwiązaniem byłoby oczywiście powtórzenie wszystkich możliwych kombinacji podanej tablicy i poszukiwanie posortowanej z największą sumą, która byłaby w Pythonie :
import itertools
def best_sum_desc_subarray(ary):
best_sum_so_far = 0
best_subarray_so_far = []
for k in range(1, len(ary)):
for comb in itertools.combinations(ary, k):
if sum(comb) > best_sum_so_far and all(comb[j] > comb[j+1] for j in range(len(comb)-1)):
best_subarray_so_far = list(comb)
best_sum_so_far = sum(comb)
return best_subarray_so_far
Niestety, ponieważ sprawdzenie czy tablica jest posortowana i obliczenie sumy na jego elementów jest i od tej operacji zostaną wykonane razy do od do , czas asymptotycznej złożoności będzie
Wyzwanie
Twoim celem jest osiągnięcie lepszej złożoności czasu niż brutalna siła powyżej. Rozwiązanie o najmniejszej asymptotycznej złożoności czasu jest zwycięzcą wyzwania. Jeśli dwa rozwiązania mają tę samą asymptotyczną złożoność czasową, zwycięzcą zostanie ten o najmniejszej asymptotycznej złożoności przestrzennej.
Uwaga: Możesz rozważyć czytanie, pisanie i porównywanie atomów nawet na dużych liczbach.
Uwaga: Jeśli istnieją dwa lub więcej rozwiązań, zwróć jedno z nich.
Przypadki testowe
Input: [200, 100, 400]
Output: [400]
Input: [4, 3, 2, 1, 5]
Output: [4, 3, 2, 1]
Input: [50, 40, 30, 20, 10]
Output: [50, 40, 30, 20, 10]
Input: [389, 207, 155, 300, 299, 170, 158, 65]
Output: [389, 300, 299, 170, 158, 65]
Input: [19, 20, 2, 18, 13, 14, 8, 9, 4, 6, 16, 1, 15, 12, 3, 7, 17, 5, 10, 11]
Output: [20, 18, 16, 15, 12, 7, 5]
Input: [14, 12, 24, 21, 6, 10, 19, 1, 5, 8, 17, 7, 9, 15, 23, 20, 25, 11, 13, 4, 3, 22, 18, 2, 16]
Output: [24, 21, 19, 17, 15, 13, 4, 3, 2]
Input: [25, 15, 3, 6, 24, 30, 23, 7, 1, 10, 16, 29, 12, 13, 22, 8, 17, 14, 20, 11, 9, 18, 28, 21, 26, 27, 4, 2, 19, 5]
Output: [25, 24, 23, 22, 17, 14, 11, 9, 4, 2]
Odpowiedzi:
Perl
Powinno to być O (n ^ 2) w czasie i O (n) w przestrzeni
Podaj liczby oddzielone spacją w jednym wierszu do STDIN
źródło
Jak to działa
bestSubarrays xs
jest sekwencją podnośników,xs
które znajdują się na efektywnej granicy {największej sumy, najmniejszego pierwszego elementu}, uporządkowanej od lewej do prawej przez zwiększenie sumy i zwiększenie pierwszego elementu.Aby przejść od
bestSubarrays xs
celubestSubarrays (x:xs)
, myx
i prawą stronę z pierwszymi elementami większymi niżx
,x
do skrajnej prawej podtablicy po lewej stronie,źródło
Ta odpowiedź rozszerza się na Ton Hospel.
Problem można rozwiązać za pomocą programowania dynamicznego za pomocą recurence
gdzie jest sekwencją wejściową, a maksymalnie osiągalną sumą dowolnej malejącej podsekwencji kończącej się indeksem . Rzeczywiste rozwiązanie można następnie odtworzyć za pomocą , jak w poniższym kodzie rdzy.T ( i ) i T(ai) T(i) i T
Wypróbuj online!
źródło