Maksymalna podtablica

Poziom trudności Łatwo
Często zadawane pytania Adobe Amazonka Apple Bloomberg ByteDance Cisco Facebook Goldman Sachs Google JP Morgan JPMorgan LinkedIn Microsoft wyrocznia PayPal Paytm Uber
Szyk Dziel i rządź Programowanie dynamiczneodwiedzajacy 136

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W zadaniu Maximum Subarray daliśmy plik liczba całkowita array nums, znajdź ciągły podrzędny szyk która ma największą sumę i wypisuje maksymalną wartość podtablicy sumy.

Przykład

Wkład
nums [] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Wydajność
6

Maksymalna podtablicaszpilka

Algorytm

Celem jest znalezienie maksymalna suma w wierszu (ciągłej pod-tablicy) w tablicy nums, co uzyskuje się za pomocą Algorytm Kadane.
Używamy dwóch zmiennych globalnych, max i maxTillNow, gdzie max przechowuje ostateczną odpowiedź, a maxTillNow przechowuje maksymalny wynik do i-tego indeksu.
Zainicjuj max i maxTillNow jako nums [0], uruchom pętlę od 1 do n, podczas każdej iteracji maxTillNow stanie się maksimum z nums [i] i (maxTillNow + nums [i]), a max stanie się maksimum z max i maxTillNow.
Na koniec zwracamy wartość max, która przechowuje maksymalną sumę podtablicy.

Analiza złożoności

Złożoność czasowa = Na) gdzie n to liczba liczb całkowitych obecnych w danej tablicy.
Złożoność przestrzeni = O (1)

Wyjaśnienie dotyczące maksymalnej podtablicy

Rozważ przypadek, w którym liczba = {2, -1, 3, 5, -2, 1}
Inicjalizuj,

  • max = nums [0] = 2 i maxTillNow = 2
  • dla i = 1, nums [i] = -1
    maxTillNow = max (-1, -1 + 2) = max (-1, 1) = 1
    max = max (2, 1) = 2
  • dla i = 2, nums [i] = 3 dla i = 4, nums [i] = -2
  • maxTillNow = max (-2, -2 + 9) = max (-2, 7) = 7
    max = max (9, 7) = 9
  • dla i = 5, nums [i] = 1
    maxTillNow = max (1, 1 + 7) = max (1, 8) = 8
    max = max (9, 8) = 9
  • Pętla się kończy i zwracamy max jako 9, co jest odpowiedzią. Tutaj 9 to nasza maksymalna suma podtablicy.

Pseudo kod

  1. Intialize max i maxTillNow jako liczby [0]
  2. pętla dla (i = 1 do mniej niż n)
  3. maxTillNow = maximum (maxTillNow + nums [i], nums [i])
  4. max = maximum (max, maxTillNow)
  5. koniec dla
  6. powrót max

Kod JAVA dla maksymalnej podtablicy

public class MaximumSubarray {
    public static void main(String[] args) {
        // Input array
        int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        
        // Find the maximum subarray using Kadane's algorithm
        int maxSum = findMaxSubarray(nums);
        
        // Print the answer
        System.out.println(maxSum);
    }
    
    private static int findMaxSubarray(int[] nums) {
        // Initialise max and maxTillNow as nums[0]
        int max = nums[0];
        int maxTillNow = nums[0];
        
        // Loop through the array
        for (int i = 1; i < nums.length; i++) {
            // maxTillNow is max of curr element or maxTillNow + curr element
            maxTillNow = Math.max(nums[i], maxTillNow + nums[i]);
            // max is maximum of max and maxTillNow
            max = Math.max(max, maxTillNow);
        }
        
        // Return the result
        return max;
    }
}

Kod C ++ dla maksymalnej podtablicy

#include <bits/stdc++.h>
using namespace std;

int findMaxSubarray(int *nums, int n) {
    // Initialise max and maxTillNow as nums[0]
    int max = nums[0];
    int maxTillNow = nums[0];
    
    // Loop through the array
    for (int i = 1; i < n; i++) {
        // maxTillNow is max of curr element or maxTillNow + curr element
        maxTillNow = std::max(nums[i], maxTillNow + nums[i]);
        // max is maximum of max and maxTillNow
        max = std::max(max, maxTillNow);
    }
    
    // Return the result
    return max;
}

int main() {
    // Input array
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    
    int n = sizeof(nums) / sizeof(*nums);
    
    // Find the maximum subarray using Kadane's algorithm
    int maxSum = findMaxSubarray(nums, n);

    // Print the answer
    cout<<maxSum<<endl;
    
    return 0;
}
{-2, 1, -3, 4, -1, 2, 1, -5, 4}
6

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »