Richest Customer Wealth

Q: Jaka jest złożoność czasowa problemu „Najbogatszy majątek klienta”?

O(m × n) dla m klientów i n banków, ponieważ każde saldo jest dodawane raz. Żaden algorytm nie może pominąć komórki, ponieważ dowolne pominięte saldo mogłoby sprawić, że jego właściciel byłby najbogatszy. Bieżące maksimum wymaga dodatkowej pamięci O(1) .

Q: Czy sumy mogą przekroczyć zakres 32-bitowej liczby całkowitej?

Nie w tym przypadku. Wiersz zawiera najwyżej 100 sald o wartości nie większej niż 10^4 , więc suma wynosi najwyżej 10^6 , czyli znacznie mniej niż 2^31 - 1 . Przy większych ograniczeniach sumę należałoby obliczać w 64-bitowej liczbie całkowitej.

PoczątkującyTablice i napisy

+10

Bank przechowuje siatkę accounts z m wierszami, po jednym dla każdego klienta, oraz n kolumnami, po jednej dla każdego banku: accounts[i][j] to kwota pieniędzy, którą klient i ma w banku j. Majątek klienta to suma wartości w jego wierszu. Zwróć majątek najbogatszego klienta.

Funkcja

maximumWealth(accounts: integer-2d-array) → integer

accountsinteger-2d-array: siatka sald, jeden wiersz na klienta i jedna kolumna na bank
Zwracainteger: największa suma wiersza

Ograniczenia

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100, a każdy wiersz ma taką samą długość.
0 ≤ accounts[i][j] ≤ 10⁴

Przykłady

Wejście: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Wyjście: 14
Wyjaśnienie: Sumy wierszy wynoszą 2 + 8 + 1 = 11, 5 + 5 + 4 = 14 oraz 7 + 0 + 3 = 10. Środkowy klient ma najwięcej, 14, mimo że największe pojedyncze saldo, 8, należy do kogoś innego.

Wejście: accounts = [[3], [9], [4]]
Wyjście: 9
Wyjaśnienie: Każdy klient korzysta z jednego banku, więc sumy wynoszą 3, 9 i 4, a odpowiedź to 9.

+14 ukrytych testów przy wysłaniu

Rozwiązanie

Każde saldo należy dokładnie do jednego klienta, więc musisz odczytać całą siatkę: żadna metoda nie jest szybsza niż O(m × n). Wybór dotyczy tego, ile zapamiętasz podczas odczytywania. Lista wszystkich sum działa, ale liczy się tylko największa suma znaleziona do tej pory, więc wystarczy jedna liczba.

Wypisz wszystkie sumy, a następnie wybierz największą

Intuicja

Podziel zadanie na dwie części. Najpierw przejdź po każdym wierszu i zsumuj jego salda, zapisując jedną sumę dla każdego klienta. W pierwszym przykładzie daje to [11, 14, 10]. Następnie przejrzyj tę listę w poszukiwaniu jej największej wartości, 14.

To rozwiązanie działa poprawnie: każde z m × n sald jest dodawane raz, a drugi przebieg odczytuje m sum. Dla siatki 100 × 100 oznacza to 10^4 dodawań. Kosztem jest sama lista — m dodatkowych liczb, które przechowujesz tylko po to, by wyrzucić wszystkie oprócz jednej.

Algorytm

Utwórz pustą listę totals.
Dla każdego wiersza dodaj jego salda i dołącz sumę do totals.
Ustaw richest na pierwszą sumę.
Zastąp richest dowolną większą sumą, a następnie ją zwróć.

def maximumWealth(accounts):
    # First pass: every customer's total wealth.
    totals = []
    for customer in accounts:
        wealth = 0
        for money in customer:
            wealth += money
        totals.append(wealth)
    # Second pass: the largest total.
    richest = totals[0]
    for wealth in totals:
        if wealth > richest:
            richest = wealth
    return richest

Utrzymuj maksimum bieżące

Intuicja

Gdy suma wiersza jest już znana, pozostaje tylko sprawdzić, czy jest większa od dotychczasowej największej sumy. Porównaj ją więc od razu i przechowuj jedną liczbę: richest. W pierwszym przykładzie richest przyjmuje kolejno wartości 0 → 11 → 14 i pozostaje równe 14, gdy suma ostatniego wiersza wynosi 10.

Ustaw początkową wartość richest na 0. To bezpieczne, ponieważ żadne saldo nie jest ujemne, więc każda suma wynosi co najmniej 0, a siatka składająca się z samych zer prawidłowo zwraca 0. Gdyby salda mogły być ujemne, początkową wartością byłaby suma pierwszego wiersza.

Największa możliwa suma to 100 × 10^4 = 10^6, więc liczba całkowita 32-bitowa może przechować każdą sumę.

Algorytm

Ustaw richest na 0.
Dla każdego wiersza zsumuj jego salda i przypisz wynik do wealth.
Jeśli wealth > richest, ustaw richest na wealth.
Po ostatnim wierszu zwróć richest.

def maximumWealth(accounts):
    richest = 0  # money is never negative, so 0 is a safe start
    for customer in accounts:
        richest = max(richest, sum(customer))
    return richest

Pułapki i przypadki brzegowe

Pętle są krótkie. Błędy wynikają z pomylenia kierunku, w którym przebiega pętla po klientach.

Sumowanie kolumn zamiast wierszy. Kolumna to jeden bank dla wszystkich klientów; jej suma odpowiada na inne pytanie. W pierwszym przykładzie sumy kolumn wynoszą 14, 13 i 8, a pierwsza z nich zgadza się z prawidłową odpowiedzią tylko przez przypadek.
Zwracanie największego pojedynczego salda. 8 to największa liczba w pierwszej siatce, ale jej właściciel ma łącznie 11, czyli mniej niż 14 klienta, który nie ma żadnego salda powyżej 5.
Resetowanie sumy wiersza w niewłaściwym miejscu. Ustaw wealth na 0 wewnątrz pętli po wierszach, przed pętlą wewnętrzną. Ustaw ją raz na zewnątrz, a każdy klient odziedziczy pieniądze poprzedniego.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu „Najbogatszy majątek klienta”?

O(m × n) dla m klientów i n banków, ponieważ każde saldo jest dodawane raz. Żaden algorytm nie może pominąć komórki, ponieważ dowolne pominięte saldo mogłoby sprawić, że jego właściciel byłby najbogatszy. Bieżące maksimum wymaga dodatkowej pamięci O(1).

Jak znaleźć maksymalną sumę wiersza w tablicy 2D?

Przejdź pętlą po wierszach, zsumuj każdy z nich i przechowuj największą sumę w zmiennej. W wielu językach można skrócić pętlę wewnętrzną za pomocą wbudowanej funkcji sumującej, takiej jak max(sum(row) for row in accounts) w Pythonie. Tak czy inaczej, odczytujesz każdą komórkę tylko raz.

Czy sumy mogą przekroczyć zakres 32-bitowej liczby całkowitej?

Nie w tym przypadku. Wiersz zawiera najwyżej 100 sald o wartości nie większej niż 10^4, więc suma wynosi najwyżej 10^6, czyli znacznie mniej niż 2^31 - 1. Przy większych ograniczeniach sumę należałoby obliczać w 64-bitowej liczbie całkowitej.

Python

def maximumWealth(accounts):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]

Oczekiwane