1672.Richest Customer Wealth

Ссылка на задачу: https://leetcode.com/problems/richest-customer-wealth/description/

Описание

Дана таблица счетов размером m x n целых чисел, где accounts[i][j] — это сумма денег, которую i-й клиент имеет в j-м банке. Необходимо вернуть состояние самого богатого клиента.

Состояние клиента — это сумма денег на всех его банковских счетах. Самый богатый клиент — это клиент с максимальным состоянием.

Примеры

Пример 1

Input:

Output: 6

Объяснение:

• состояние первого клиента = 1 + 2 + 3 = 6

• состояние второго клиента = 3 + 2 + 1 = 6

Оба клиента имеют одинаковое состояние 6, поэтому ответ - 6

Пример 2

Input:

Output: 10

Объяснение:

• состояние первого клиента = 1 + 5 = 6

• состояние второго клиента = 7 + 3 = 10

• состояние третьего клиента = 3 + 5 = 8

Максиммум из 6, 10 и 8 - это 10

Ограничения

• m == accounts.length

• n == accounts[i].length

• 1 <= m, n <= 50

• nums.length == 2n

• 1 <= accounts[i][j] <= 100

Решение

Каждая строка матрицы содержит количество денег одного конкретного клиента в каждом из банков по отдельности. Так, для подсчета состояния клиента i-того достаточно сложить все элементы i-той строки. При этом можно отслеживать, больше ли только что посчитанное состояние заранее инициализированного максимума.

Алгоритм:

1. Инициализировать искомый максимум нулем (при инициализации максимум берем в соответствии с минимальным значением и ограничений)

2. Итерируемся по строкам матрицы

3. Подсчитываем сумму элементов текущей строки и сравниваем с максимумом

4. Если максимум меньше суммы, то обновляем его

Код:

python

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        maxx = 0
        for i in range(len(accounts)):
            summa = sum(accounts[i])
            if summa > maxx:
                maxx = summa
        return maxx

C++

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int maxx = 0;
        for (vector<int>& acc : accounts) {
            int summa = accumulate(acc.begin(), acc.end(), 0);
            if (summa > maxx) {
                maxx = summa;
            }
        }
        return maxx;
    }
};

Сложность алгоритма по времени - O(N*M)

Для решения требуется полный перебор всех строк, количество которых равно m. Для подсчета суммы на каждой итерации требуется перебрать все элементы строки, их количество - n. Результирующая сложность - O(N*M).

Сложность алгоритма по памяти - O(1)

Для решения не используется дополнительных объектов.