Maximum Sum Subarray of Size K

Q: Czym jest przesuwne okno o stałym rozmiarze?

To zakres dokładnie k sąsiadujących elementów, który przesuwa się po tablicy o jeden krok naraz. Zamiast za każdym razem obliczać zakres od nowa, aktualizujesz bieżącą wartość: dodajesz element, który pojawia się z prawej strony, i usuwasz ten, który znika z lewej. Dzięki temu praca o złożoności O(n·k) zmienia się w pracę o złożoności O(n) .

Q: Jaka jest złożoność czasowa maksymalnej sumy podtablicy o rozmiarze k?

Przy użyciu okna przesuwnego złożoność czasowa wynosi O(n) , a dodatkowa złożoność pamięciowa O(1) : jedno przejście, aby zsumować elementy pierwszego okna, a następnie jedno dodawanie i jedno odejmowanie na każdym kroku. Osobne sumowanie każdego okna wymaga (n-k+1) × k dodawań, czyli O(n·k) , około 2.5 × 10^7 dla n = 10^4 i k = 5000 .

Q: czym różni się to od problemu maksymalnej podtablicy?

Tutaj długość jest stała i wynosi k , więc każdy kandydat jest oknem, a suma krocząca obejmuje je wszystkie. W problemie maksymalnej podtablicy długość jest dowolna i potrzebujesz algorytmu Kadane’a, który przy każdym elemencie decyduje, czy przedłużyć bieżący ciąg, czy rozpocząć nowy. Stałe okno nigdy nie daje takiego wyboru.

Q: Czy sumy prefiksowe też mogą to rozwiązać?

Tak. Zbuduj prefix[i] jako sumę pierwszych i elementów, a suma okna zaczynającego się od s wynosi prefix[s+k] - prefix[s] . To również zajmuje O(n) czasu, ale przechowuje n+1 sum. Pętla przesuwnego okna oblicza te same sumy za pomocą dwóch zmiennych.

ŁatwePrzesuwane okno

+10

Otrzymujesz tablicę liczb całkowitych nums i długość okna k. Sprawdź każdy ciąg dokładnie k sąsiadujących elementów i zwróć największą sumę spośród nich. Wartości mogą być ujemne, więc odpowiedź również może być ujemna.

Funkcja

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: tablica liczb całkowitych
kinteger: ile sąsiadujących elementów zawiera każde okno
Zwracainteger: największa suma dowolnych k kolejnych elementów

Ograniczenia

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Przykłady

Wejście: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Wyjście: 10
Wyjaśnienie: Pięć okien o długości 3 daje w sumie 6, 9, 8, 10 i 4. Największa suma to 7 + (-2) + 5 = 10.

Wejście: nums = [-3, -8, -1, -6]k = 2
Wyjście: -7
Wyjaśnienie: Każda wartość jest ujemna, więc każda suma okna również jest ujemna: -11, -9 i -7. Największa z nich to -1 + (-6) = -7.

Wejście: nums = [5, -2, 4]k = 3
Wyjście: 7
Wyjaśnienie: Gdy k jest równe długości tablicy, istnieje jedno okno — cała tablica — a 5 + (-2) + 4 = 7.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz również zwrócić pozycję, w której zaczyna się najlepsze okno, wybierając najbardziej lewe, jeśli kilka okien ma taki sam wynik?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Jest n-k+1 okien, a obliczenie sumy każdego z nich od zera wymaga k dodawań. Sztuczka polega na tym, że dwa sąsiednie okna różnią się tylko dwoma elementami. Przesuwaj okno zamiast obliczać je od nowa: jedna wartość wchodzi, jedna wychodzi, a obliczenie sumy każdego okna wymaga dwóch operacji.

Dodaj do siebie wszystkie okna

Poprawne, ale nie kończy się na największych testach

Intuicja

Okno jest wyznaczone przez miejsce, w którym się zaczyna. Może zaczynać się od indeksu 0, 1 i tak dalej aż do n-k, ponieważ późniejszy początek wykraczałby poza koniec tablicy. Dla każdego początku dodaj k elementów i porównaj sumę z najlepszym dotychczas wynikiem.

Dla [4, -1, 3, 7, -2, 5, 1] i k = 3 otrzymujemy sumy 6, 9, 8, 10, 4, a odpowiedzią jest 10. Ustaw najlepszy wynik na sumę pierwszego okna lub na najmniejszą liczbę całkowitą, nigdy na 0: gdy wszystkie wartości są ujemne, 0 byłoby większe od sumy każdego rzeczywistego okna.

Koszt to (n-k+1) × k dodawań. Jest największy, gdy k wynosi mniej więcej połowę n: dla n = 10^4 i k = 5000 daje to 5001 × 5000, czyli około 2.5 × 10^7 dodawań, z których niemal wszystkie powtarzają pracę wykonaną już dla poprzedniego okna.

Algorytm

Ustaw best na najmniejszą możliwą wartość.
Dla każdego początku od 0 do n-k ustaw total = 0.
Dodaj do total wartości od nums[start] do nums[start+k-1].
Jeśli total jest większe niż best, zapisz tę wartość.
Zwróć best.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Przesuń okno o stałej wielkości

Intuicja

Porównaj okno zaczynające się od indeksu 0 z oknem zaczynającym się od indeksu 1. W [4, -1, 3, 7, -2, 5, 1] dla k = 3 są to 4 + (-1) + 3 = 6 oraz (-1) + 3 + 7 = 9. Oba zawierają -1 i 3. Druga suma to pierwsza suma powiększona o wartość, która weszła, 7, i pomniejszona o wartość, która wyszła, 4: 6 + 7 - 4 = 9.

To działa przy każdym kroku. Gdy prawy koniec okna przesuwa się na indeks i, element na pozycji i wchodzi, a element na pozycji i-k wychodzi. Dodajesz więc elementy pierwszego okna tylko raz, a następnie aktualizujesz sumę, wykonując jedno dodawanie i jedno odejmowanie na krok. Sumy wynoszą 6, 9, 8, 10, 4, tak samo jak przy użyciu metody brute force, a ty zachowujesz największą z nich.

Każdy element wchodzi raz i wychodzi co najwyżej raz, więc złożoność czasowa wynosi O(n). Przechowujesz dwie liczby: sumę bieżącego okna i największą sumę, więc dodatkowa przestrzeń wynosi O(1). Żadna z tych sum nie przekracza 10^4 × 10^4 = 10^8, więc wystarczy 32-bitowa liczba całkowita.

Algorytm

Dodaj do window wartości od nums[0] do nums[k-1].
Ustaw best = window.
Dla każdego i od k do n-1 dodaj nums[i] i odejmij nums[i-k].
Po każdym kroku ustaw best na większą z wartości best i window.
Zwróć best.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Pułapki i przypadki brzegowe

Pomysł z oknem jest prosty, więc błędy kryją się w wartościach początkowych i indeksach.

Ustawienie best na 0. Dla [-3, -8, -1, -6] i k = 2 prawidłowy wynik to -7, ale wartości best równej 0 nie da się pobić, więc zostanie zwrócona jako wynik.
Odejmowanie niewłaściwego elementu. Gdy do okna wchodzi nums[i], wychodzi z niego nums[i-k]. Użycie nums[i-k+1] lub nums[i-k-1] daje okna o niewłaściwej długości.
Zatrzymanie brute force o jeden początek za wcześnie. Ostatnie okno zaczyna się przy n-k, więc pętla musi uwzględniać tę pozycję. Gdy k = n, jest to jedyne okno, a błąd o jeden sprawia, że nie zostaje sprawdzone żadne okno i zwracana jest początkowa wartość best.
Porównywanie dopiero po pętli. Najlepsze okno może być pierwsze, więc porównaj także pierwszą sumę albo zainicjalizuj best jej wartością.
Zapominanie, że indeksowanie w R i Lua zaczyna się od 1. Pierwsze okno to nums[1..k], a element, który opuszcza okno, gdy wchodzi do niego nums[i], to nadal nums[i-k].

Najczęstsze pytania4

Czym jest przesuwne okno o stałym rozmiarze?

To zakres dokładnie k sąsiadujących elementów, który przesuwa się po tablicy o jeden krok naraz. Zamiast za każdym razem obliczać zakres od nowa, aktualizujesz bieżącą wartość: dodajesz element, który pojawia się z prawej strony, i usuwasz ten, który znika z lewej. Dzięki temu praca o złożoności O(n·k) zmienia się w pracę o złożoności O(n).

Jaka jest złożoność czasowa maksymalnej sumy podtablicy o rozmiarze k?

Przy użyciu okna przesuwnego złożoność czasowa wynosi O(n), a dodatkowa złożoność pamięciowa O(1): jedno przejście, aby zsumować elementy pierwszego okna, a następnie jedno dodawanie i jedno odejmowanie na każdym kroku. Osobne sumowanie każdego okna wymaga (n-k+1) × k dodawań, czyli O(n·k), około 2.5 × 10^7 dla n = 10^4 i k = 5000.

czym różni się to od problemu maksymalnej podtablicy?

Tutaj długość jest stała i wynosi k, więc każdy kandydat jest oknem, a suma krocząca obejmuje je wszystkie. W problemie maksymalnej podtablicy długość jest dowolna i potrzebujesz algorytmu Kadane’a, który przy każdym elemencie decyduje, czy przedłużyć bieżący ciąg, czy rozpocząć nowy. Stałe okno nigdy nie daje takiego wyboru.

Czy sumy prefiksowe też mogą to rozwiązać?

Tak. Zbuduj prefix[i] jako sumę pierwszych i elementów, a suma okna zaczynającego się od s wynosi prefix[s+k] - prefix[s]. To również zajmuje O(n) czasu, ale przechowuje n+1 sum. Pętla przesuwnego okna oblicza te same sumy za pomocą dwóch zmiennych.

Python

def maxSumSubarray(nums, k):
    # Wpisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Oczekiwane