Zliczanie liczby sum z przyległych podtablic tablicy

12

Otrzymujemy tablicę ze wszystkimi .a[1n]a[i]>0

Teraz musimy dowiedzieć się, ile różnych sum można uformować z jego podstron (gdzie podtablica to ciągły zakres tablicy, tj. dla niektórych , suma jest sumą wszystkich elementy podtablicy). Na przykład, jeśli , to odpowiedź brzmi 4: możemy utworzyć .a[jk]j,ka=[1,2,1]1,2,3,4

Wiem, jak policzyć liczbę odrębnych sum w czasie .O(n2)

Ponadto zdałem sobie sprawę, że jest to podobne do klasycznego problemu, w którym musimy znaleźć liczbę różnych podciągów łańcucha. Myślałem o możliwości skonstruowania tablicy sufiksów i rozwiązania jej w podobny sposób (w czasie ). Ale nie byłem w stanie dowiedzieć się, jak to zmienić, aby działało tutaj. Na przykład, jeśli użyjemy tablicy sufiksów dla , otrzymamy 5 przypadków zamiast czterech dopuszczalnych. Czy można to zrobić za pomocą tablic przyrostków, czy też myślę w złym kierunku?O(n)a=[1,2,1]

Myślę też o jednym kierunku. Dziel i podbijaj. Jakbym za każdym razem dzielił tablicę na dwie części, dopóki nie zostanie zredukowana do jednego elementu. Pojedynczy element może mieć jedną sumę. Teraz, jeśli połączymy dwa pojedyncze elementy, można to zrobić na dwa sposoby: jeśli oba pojedyncze zakresy mają ten sam element, otrzymamy 2 różne sumy, lub jeśli oba mają różne elementy, otrzymamy 3 różne sumy. Ale nie jestem w stanie uogólnić tego dla scalania tablic o długości większej niż 1. Czy jest możliwe scalenie dwóch tablic o rozmiarze m i uzyskanie odpowiedzi w ?O(m)

Salena
źródło
Chociaż nie od razu widzę, jak można z niego wyciągnąć rozwiązanie swojego problemu, struktura problemu maksymalnej podtablicy jest podobna do opisywanego problemu i ma rozwiązanie dzielenia i zdobywania, które działa w . O(n lg n)
Isaac Kleinman
Sugerowałbym zacząć od następującego problemu: jak trudno jest zdecydować, czy istnieją dwa przedziały o tej samej sumie? Kuszące jest udowodnienie twardości 3SUM tego problemu, ale jak dotąd nie byłem w stanie.
Yuval Filmus

Odpowiedzi:

2

W najgorszym przypadku prawie na pewno nie można uzyskać lepszej wartości niż ponieważ liczba różnych sum może być w .O(n2)Θ(n2)

Rozważ np. Tablicę . Tutaj każda z sąsiednich podrzędnych ma inną sumę.[1,2,4,8,,2n]n(n+1)2


„Prawie na pewno” wynika z faktu, że problem nie wymaga wartości sum jako danych wyjściowych. Jednak nie sądzę, że duplikatów można uniknąć bez określenia przynajmniej większości wartości.

FrankW
źródło
Nie widzę żadnego szczególnego powodu, dla którego nie powinno być sposobu, aby w jakiś sposób ominąć wszystkie możliwości, a jednocześnie znaleźć właściwą odpowiedź. Algorytmy programowania dynamicznego robią to rutynowo.
Yuval Filmus