Zacznijmy od następującej obserwacji:
Niech max oznacza maksimum sekwencji a1,...,an , a niech min oznacza minimum. Jeśli a1=max , Optymalne jest wybranie b1=b2=...=bn=⌊(max+min)/2⌋ .
Dlaczego tak jest? Cóż, ponieważ sekwencja zaczyna się od maksimum, albo wybieramy b1 duże i cierpimy na duże odchylenie od minimum sekwencji (ponieważ każde kolejne bi musi być większe lub równe b1 ), lub wybieramy b1 małe i cierpimy na odchylenie do max . Średnia minimalizuje maksymalne odchylenie.
Możemy teraz spróbować uogólnić to spostrzeżenie, aby zastosować je w ogólnych sekwencjach a1,...,an . Na przykład, możemy podzielić dowolną sekwencję na podsekwencje, tak aby każda zaczynała się od maksimum odpowiedniej podsekwencji.
Przykład: dzieli się na , i .( 2 ) ( 6 , 4 , 1 , 5 , 2 ) ( 8 , 7 , 5 , 1 )(2,6,4,1,5,2,8,7,5,1)(2)(6,4,1,5,2)(8,7,5,1)
Biorąc pod uwagę ten podział, możemy teraz rozwiązać każdy z tych podsekwencji osobno i uzyskać przypisanie , co może jednak naruszać warunek nie malejący. Można to naprawić bez utraty optymalności.bi
Zauważ, że ostatni podsekwencja zawsze zawiera maksymalne całej sekwencji (w przeciwnym razie po niej pojawiłaby się kolejna podsekwencja). Niech być przypisane wartości mamy do podciągów. Teraz, aby osiągnąć nie zmniejszanie w , zaczynamy od tyłu w i do przodu. Jeśli jest większy niż , po prostu ustawiamy . Jeśli jest mniejszy, zachowujemy go. Następnie przechodzimy do porównania z i tak dalej. Zauważ, że obniżenie dowolnego do wartościw 1 , w 2 , . . . , W k k wagowo 1 , . . . , w k w k w k - 1 w k w k - 1 : = w k w k - 2 w k - 1 w i w i + 1 w i w i + 1maxw1,w2,...,wkkw1,...,wkwkwk−1wkwk−1:=wkwk−2wk−1wiwi+1nigdy nie zwiększa odchylenia, ponieważ wartość maksymalna w podsekwencji przypisanej za pomocą jest zawsze niższa niż maksymalna w podsekwencji przypisanej za pomocą .wiwi+1
Myślę, że ten algorytm powinien być poprawny. Jeśli chodzi o czas wykonywania, kluczowym krokiem jest obliczenie rosnących maksimów dla podsekwencji, co jest możliwe w ? Nie jestem pewien, gdzie przyczynia się.lO(n)l
Myślę, że powinno to być wykonalne w O (n).
Podejmij podobny problem: Biorąc pod uwagę , 1 ≤ i ≤ n oraz d ≥ 0, znajdź w kolejności malejącej, tak że dla wszystkich i lub pokaż, że nie jest to możliwe. Można to zrobić w O (n), a przy użyciu wyszukiwania binarnego oryginalny problem rozwiązuje się w O (n log l).b i | a i - b i | ≤ dai bi |ai−bi|≤d
Teraz, jeśli są i ≤ j takie, że a_i - a_j> 2d, to nie ma rozwiązania (ponieważ ).bi≥ai−d,bj≤aj+d<ai−2d+d=ai−d≤bi
Ale jeśli a_i - a_j ≤ 2d dla wszystkich i ≤ j, to myślę, że zawsze znajdzie się rozwiązanie. Więc wszystko, co musimy zrobić, to znaleźć m = max (a_i - a_j) dla wszystkich i ≤ j, i wybrać d = floor ((m + 1) / 2). To maksimum można znaleźć w O (n).
źródło