Największa suma podzielna przez n

Zadałem to pytanie na StackOverflow , ale myślę, że tutaj jest bardziej odpowiednie miejsce.

Jest to problem od kursu Wprowadzenie do algorytmów :

Musisz tablicę $a$ z liczb całkowitych dodatnich (tablica nie muszą być sortowane lub elementów unikalnych). Zaproponuj algorytm , aby znaleźć największą sumę elementów, która jest podzielna przez .$n$$O(n)$$n$

Przykład: . Odpowiedź to (z elementami )$a = [6, 1, 13, 4, 9, 8, 25], n = 7$$56$$6, 13, 4, 8, 25$

Stosunkowo dynamicznie jest go znaleźć w przy użyciu programowania dynamicznego i przechowując największą sumę z resztą .$O(n^2)$$0, 1, 2,..., n - 1$

Ponadto, jeśli ograniczenia uwagę na ciągłej sekwencji elementów, łatwo znaleźć optymalną takiej sekwencji w czasie przechowywania cząstkowych sumy modulo niech , dla każdej reszty pamiętaj największy indeks taki, że , a następnie dla każdego rozważasz S [j] -S [i] gdzie j jest indeksem odpowiadającym r = S [i] \ bmod n .$O(n)$$n$$S[i]=a[0]+a[1]+\dots + a[i]$$r$$j$$S[j] \equiv r \pmod{n}$$i$$S[j]-S[i]$$j$$r=S[i] \bmod n$

Ale czy istnieje rozwiązanie czasu $O(n)$ w przypadku ogólnym? Wszelkie sugestie będą mile widziane! Myślę, że ma to coś wspólnego z algebrą liniową, ale nie jestem pewien, co dokładnie.

Alternatywnie, czy można to zrobić w czasie $O(n \log n)$ ?

Oto kilka przypadkowych pomysłów:

• Algorytm programowania dynamicznego można przerzucić, aby wyszukać najmniejszą sumę zamiast największej. Po prostu kończysz na szukaniu sumy zgodnej z resztą sumy całej tablicy, zamiast jednej przystawki do zera. Jeśli przetwarzamy elementy w kolejności rosnącej, czasami pozwala to na zakończenie algorytmu dynamicznego przed przetworzeniem całej tablicy.

  Koszt wyniósłby , gdybyśmy przetworzyli elementów. W tym algorytmie nie ma dolnej granicy , ponieważ nie musimy sortować wszystkich elementów. Zajmuje tylko czas, aby uzyskać najmniejszych elementów.$O(n k)$$k$$\Omega(n \log n)$$O(n \log k)$$k$

• Jeśli zależy nam na zbiorze o dużych rozmiarach, zamiast zestawu o największej sumie, możemy być w stanie użyć mnożenia wielomianowego opartego na szybkiej transformacie Fouriera, aby rozwiązać problem w czas. Podobne do tego, co zrobiono w 3SUM, gdy zakres domen jest ograniczony. (Uwaga: użyj powtarzania kwadratu, aby przeprowadzić wyszukiwanie binarne, w przeciwnym razie otrzymasz gdzie jest liczbą pominiętych elementów.)$O(n (\log n)^2 (\log \log n))$$O(n k (\log n) (\log \log n))$$k$

• Gdy jest złożone, a prawie wszystkie pozostałe są wielokrotnością jednego z czynników , można zaoszczędzić znaczny czas, skupiając się na pozostałych, które nie są wielokrotnością tego czynnika.$n$$n$

• Gdy reszta rjest bardzo powszechna lub pozostało tylko kilka, śledzenie „następnego otwartego slotu, jeśli zaczniesz od tego miejsca i będziesz przechodzić dalej r”, może zaoszczędzić wiele skanowania w poszukiwaniu skoków w otwarte miejsca czas.

• Możesz ogolić współczynnik logarytmiczny, śledząc jedynie osiągalność i używając masek bitowych (w odwróconym algorytmie dynamicznym), a następnie cofając się po osiągnięciu pozostałej wartości docelowej.

• Algorytm programowania dynamicznego jest bardzo podatny na równoległe działanie. Z procesorem dla każdego gniazda bufora możesz przejść do . Alternatywnie, używając szerokości oraz dzielenia i zdobywania agregacji zamiast agregacji iteracyjnej, koszt głębokości obwodu może spaść aż do .$O(n)$$O(n^2)$$O(\log^2 n)$

• (Meta) Podejrzewam, że podany przez ciebie problem dotyczy ciągłych sum. Jeśli powiązałeś się z rzeczywistym problemem, łatwo byłoby to zweryfikować. W przeciwnym razie jestem bardzo zaskoczony, jak trudny jest ten problem, biorąc pod uwagę, że został on przypisany w kursie o nazwie „Wprowadzenie do algorytmów”. Ale może omówiłeś w klasie sztuczkę, która czyni ją trywialną.

Mój proponowany algorytm wygląda następująco:

Suma dzieli się przez n, jeśli dodasz tylko sumy będące wielokrotnościami n.

Zanim zaczniesz, tworzysz mapę z int jako kluczem i listą indeksów jako wartością. Tworzysz także listę wyników zawierającą indeksy.

Następnie zapętlasz tablicę i dodajesz każdy indeks, którego mod n wynosi zero, do listy wyników. Dla każdego innego indeksu wykonaj następujące czynności:

Odejmujesz wartość mod n tego indeksu od n. Ten wynik jest kluczem do twojego hashapa, który przechowuje indeksy dla elementów o wymaganej wartości. Teraz dodajesz ten indeks do listy w haszapie i idziesz dalej.

Po zakończeniu zapętlania tablicy macierz oblicza dane wyjściowe. Robisz to, sortując każdą listę w haszapie zgodnie z wartością wskazywaną przez indeks. Teraz weźmiesz pod uwagę każdą parę w haszpie sumującą się do n. Więc jeśli n = 7, przeszukujesz hashap dla 3 i 4. Jeśli masz wpis w obu, bierzesz dwie największe wartości, usuwasz je z ich list i dodajesz do swojej listy wyników.

Ostatnia rekomendacja: nadal nie testowałem algorytmu, napisz test z nim za pomocą algorytmu brutalnej siły.

użyj tej metody DP z ( /programming/4487438/maximum-sum-of-non-consecutive-elements?rq=1 ):

Biorąc pod uwagę tablicę A [0..n], niech M (i) będzie optymalnym rozwiązaniem wykorzystującym elementy o indeksach 0..i. Następnie M (-1) = 0 (użyte w nawrocie), M (0) = A [0], a M (i) = max (M (i - 1), M (i - 2) + A [i ]) dla i = 1, ..., n. M (n) to rozwiązanie, którego chcemy. To jest O (n) . Możesz użyć innej tablicy do zapisania wyboru dokonanego dla każdego podproblemu, aby odzyskać wybrane elementy.

Zmień rekurencję na M (i) = max (M (i - 1), M (i - 2) + A [i]) tak, że jest przechowywana tylko wtedy, gdy jest podzielna przez N