Richest Customer Wealth

Q: Какова временная сложность задачи «Богатство самого состоятельного клиента»?

O(m × n) для m клиентов и n банков, поскольку каждый баланс складывается один раз. Ни один алгоритм не может пропустить ячейку, поскольку любой пропущенный баланс может оказаться тем, который сделает его владельца самым богатым. Для текущего максимума требуется дополнительная память O(1) .

Q: Могут ли суммы переполнить 32-разрядное целое число?

Нет, не здесь. В строке не более 100 балансов, каждый из которых не превышает 10^4 , поэтому сумма не превышает 10^6 , что намного меньше 2^31 - 1 . При больших ограничениях следовало бы складывать значения в 64-битное целое число.

НовичокМассивы и строки

+10

Банк хранит таблицу accounts с m строками — по одной на каждого клиента — и n столбцами — по одному на каждый банк: accounts[i][j] — это сумма денег, которую клиент i хранит в банке j. Состояние клиента — это сумма значений в его строке. Верните состояние самого богатого клиента.

Функция

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

accountsinteger-2d-array: сетка балансов: одна строка на клиента и один столбец на банк
Возвращаетinteger: наибольшая сумма в строке

Ограничения

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100, и все строки имеют одинаковую длину.
0 ≤ accounts[i][j] ≤ 10⁴

Примеры

Ввод: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Вывод: 14
Пояснение: Суммы по строкам равны 2 + 8 + 1 = 11, 5 + 5 + 4 = 14 и 7 + 0 + 3 = 10. У среднего клиента сумма наибольшая — 14, хотя самый большой отдельный баланс, 8, принадлежит кому-то другому.

Ввод: accounts = [[3], [9], [4]]
Вывод: 9
Пояснение: Каждый клиент пользуется одним банком, поэтому итоги — 3, 9 и 4, а ответ — 9.

+14 скрытых тестов при отправке

Решение

Каждый баланс принадлежит ровно одному клиенту, поэтому нужно прочитать всю таблицу: ни один подход не превзойдёт O(m × n) по времени. Вопрос лишь в том, сколько данных сохранять во время чтения. Список всех сумм подойдёт, но важна только наибольшая сумма из уже встреченных, поэтому достаточно одного числа.

Перечислите все суммы, затем выберите наибольшую

Идея

Раздели задачу на две части. Сначала пройди по каждой строке и сложи её балансы, сохраняя по одному итогу для каждого клиента. Для первого примера получится [11, 14, 10]. Затем найди в этом списке наибольшее значение — 14.

Вычисления выполнены корректно: каждый из m × n балансов складывается один раз, а второй проход считывает m итогов. Для сетки размером 100 × 100 это 10^4 сложений. Цена за это — сам список: m дополнительных чисел, которые ты хранишь, только чтобы в итоге отбросить все, кроме одного.

Алгоритм

Создай пустой список totals.
Для каждой строки сложи её балансы и добавь сумму в totals.
Присвой richest первое значение из списка итогов.
Замени richest на любое большее значение, затем верни его.

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

Поддерживайте текущий максимум

Идея

Когда сумма строки известна, остаётся только выяснить, превышает ли она наибольшую сумму на данный момент. Поэтому сразу сравнивай её и храни одно число — richest. В первом примере richest принимает значения 0 → 11 → 14 и остаётся равным 14, когда сумма последней строки равна 10.

Начни со значения 0 для richest. Это безопасно, потому что ни один баланс не отрицательный, поэтому каждая сумма не меньше 0, и сетка из нулей правильно возвращает 0. Если бы балансы могли быть отрицательными, ты бы начал с суммы первой строки.

Наибольшая возможная сумма равна 100 × 10^4 = 10^6, поэтому 32-битное целое число вмещает любую сумму.

Алгоритм

Установи richest в значение 0.
Для каждой строки сложи её балансы в wealth.
Если wealth > richest, установи richest в значение wealth.
После последней строки верни 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

Ловушки и крайние случаи

Циклы короткие. Ошибки возникают, если перепутать, в каком направлении записан каждый клиент.

Суммирование столбцов вместо строк. Столбец — это один банк для всех клиентов; его сумма отвечает на другой вопрос. В первом примере суммы столбцов равны 14, 13 и 8, и первое значение совпадает с правильным ответом лишь случайно.
Возвращение наибольшего отдельного баланса. 8 — наибольшее число в первой таблице, но у его владельца в сумме 11, что меньше 14 у клиента, у которого ни в одном банке баланс не превышает 5.
Сброс суммы строки не в том месте. Присвойте wealth значение 0 внутри цикла по строкам, перед внутренним циклом. Если присвоить его один раз снаружи, каждый клиент унаследует деньги предыдущего.

Частые вопросы3

Какова временная сложность задачи «Богатство самого состоятельного клиента»?

O(m × n) для m клиентов и n банков, поскольку каждый баланс складывается один раз. Ни один алгоритм не может пропустить ячейку, поскольку любой пропущенный баланс может оказаться тем, который сделает его владельца самым богатым. Для текущего максимума требуется дополнительная память O(1).

Как найти максимальную сумму элементов строки в двумерном массиве?

Перебирай строки, суммируй каждую и сохраняй наибольшую сумму в переменной. Во многих языках внутренний цикл сокращают с помощью встроенной функции sum, например max(sum(row) for row in accounts) в Python. В любом случае ты считываешь каждую ячейку один раз.

Могут ли суммы переполнить 32-разрядное целое число?

Нет, не здесь. В строке не более 100 балансов, каждый из которых не превышает 10^4, поэтому сумма не превышает 10^6, что намного меньше 2^31 - 1. При больших ограничениях следовало бы складывать значения в 64-битное целое число.

Python

def maximumWealth(accounts):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

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

Ожидается