Richest Customer Wealth

Q: Qual é a complexidade de tempo de Richest Customer Wealth?

O(m × n) para m clientes e n bancos, porque cada saldo é somado uma vez. Nenhum algoritmo pode pular uma célula, pois qualquer saldo ignorado poderia ser aquele que torna seu proprietário o mais rico. O máximo corrente usa O(1) de espaço extra.

Q: As somas podem causar overflow em um inteiro de 32 bits?

Não neste caso. Uma linha tem no máximo 100 saldos de no máximo 10^4 , então o total é no máximo 10^6 , muito abaixo de 2^31 - 1 . Com limites maiores, você somaria em um inteiro de 64 bits.

InicianteArrays e strings

+10

Um banco mantém uma grade accounts com m linhas, uma por cliente, e n colunas, uma por banco: accounts[i][j] é o dinheiro que o cliente i tem no banco j. A riqueza de um cliente é o total da sua linha. Retorne a riqueza do cliente mais rico.

Função

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

accountsinteger-2d-array: a grade de saldos, uma linha por cliente e uma coluna por banco
Retornainteger: o maior total de linha

Restrições

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100, e todas as linhas têm o mesmo comprimento.
0 ≤ accounts[i][j] ≤ 10⁴

Exemplos

Entrada: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Saída: 14
Explicação: As linhas somam 2 + 8 + 1 = 11, 5 + 5 + 4 = 14 e 7 + 0 + 3 = 10. O cliente do meio tem o maior total, 14, embora o maior saldo individual, 8, pertença a outra pessoa.

Entrada: accounts = [[3], [9], [4]]
Saída: 9
Explicação: Cada cliente usa um banco, então os totais são 3, 9 e 4, e a resposta é 9.

+14 testes ocultos ao enviar

Solução

Cada saldo pertence a exatamente um cliente, então você precisa ler toda a grade: nenhuma abordagem supera o tempo O(m × n). A escolha é quanto você mantém enquanto lê. Uma lista com todos os totais funciona, mas apenas o maior total visto até agora importa, então um único número é suficiente.

Liste cada total e, em seguida, escolha o maior

Intuição

Divida a tarefa em duas partes. Primeiro, percorra cada linha e some seus saldos, armazenando um total por cliente. Para o primeiro exemplo, isso resulta em [11, 14, 10]. Depois, percorra essa lista em busca do maior valor, 14.

O trabalho está correto: cada um dos m × n saldos é somado uma vez, e a segunda passagem lê m totais. Para uma grade de 100 × 100, são 10^4 somas. O custo é a própria lista: m números extras que você mantém apenas para descartar todos, exceto um.

Algoritmo

Crie uma lista vazia totals.
Para cada linha, some os saldos e acrescente a soma a totals.
Comece richest com o primeiro total.
Substitua richest por qualquer total maior e, em seguida, retorne-o.

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

Mantenha um máximo acumulado

Intuição

Depois que o total de uma linha é conhecido, a única questão é saber se ele supera o melhor total até então. Portanto, compare-o imediatamente e mantenha um único número, richest. No primeiro exemplo, richest passa por 0 → 11 → 14 e permanece em 14 quando a última linha soma 10.

Comece richest em 0. Isso é seguro porque nenhum saldo é negativo, então todo total é pelo menos 0, e uma grade de zeros retorna corretamente 0. Se os saldos pudessem ser negativos, você começaria pelo total da primeira linha.

O maior total possível é 100 × 10^4 = 10^6, então um inteiro de 32 bits comporta todas as somas.

Algoritmo

Defina richest como 0.
Para cada linha, some os saldos em wealth.
Se wealth > richest, defina richest como wealth.
Após a última linha, retorne 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

Armadilhas e casos extremos

Os loops são curtos. Os bugs surgem quando se confunde a direção em que cada cliente está.

Somar colunas em vez de linhas. Uma coluna é um banco para todos os clientes; seu total responde a uma pergunta diferente. No primeiro exemplo, as colunas somam 14, 13 e 8, e a primeira só coincide com a resposta correta por sorte.
Retornar o maior saldo individual. 8 é o maior número na primeira grade, mas seu titular tem 11 no total, menos que os 14 do cliente que não tem nenhum saldo acima de 5.
Redefinir o total da linha no lugar errado. Defina wealth como 0 dentro do loop da linha, antes do loop interno. Defina-o uma vez fora, e cada cliente herda o dinheiro do anterior.

Perguntas frequentes3

Qual é a complexidade de tempo de Richest Customer Wealth?

O(m × n) para m clientes e n bancos, porque cada saldo é somado uma vez. Nenhum algoritmo pode pular uma célula, pois qualquer saldo ignorado poderia ser aquele que torna seu proprietário o mais rico. O máximo corrente usa O(1) de espaço extra.

Como encontrar a soma máxima das linhas de um array bidimensional?

Percorra as linhas, some cada uma e mantenha a maior soma em uma variável. Muitas linguagens simplificam o loop interno com uma função sum integrada, como max(sum(row) for row in accounts) em Python. De qualquer forma, você lê cada célula uma vez.

As somas podem causar overflow em um inteiro de 32 bits?

Não neste caso. Uma linha tem no máximo 100 saldos de no máximo 10^4, então o total é no máximo 10^6, muito abaixo de 2^31 - 1. Com limites maiores, você somaria em um inteiro de 64 bits.

Python

def maximumWealth(accounts):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

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

Esperado