Richest Customer Wealth
一家银行有一个 accounts 网格，其中有 m 行，每行对应一位客户；有 n 列，每列对应一家银行：accounts[i][j] 表示客户 i 在银行 j 持有的钱。一位客户的财富是其所在行的总和。返回最富有客户的财富。
函数
- accountsinteger-2d-array
- 余额网格，每位客户占一行，每家银行占一列
- 返回值integer
- 最大的行总计
约束条件
1 ≤ accounts.length ≤ 1001 ≤ accounts[i].length ≤ 100，并且每一行的长度都相同。0 ≤ accounts[i][j] ≤ 104
示例
- 输入
- accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
- 输出
- 14
- 解释
- 各行的总和分别是
11、14和10。中间那位客户最富有，总额为14，尽管最大的单笔余额8属于其他人。
- 输入
- accounts = [[3], [9], [4]]
- 输出
- 9
- 解释
- 每位客户都使用一家银行，因此总数是
3、9和4，答案是9。
提示
逐个打开提示，每个都会多透露一点。
哪些数字属于同一位客户：网格中的一行还是一列？
把每一行的数值相加，就能得到一位客户的财富。你不需要同时处理两行。
保留一个变量，用来记录目前为止最大的总和。计算一行的总和，进行比较，然后继续处理下一行。
题解
每个余额都恰好属于一位客户，因此你必须读取整个网格：没有任何方法能比 O(m × n) 更快。关键在于读取时保留多少信息。目前只需要关注已看到的最大总额，所以只用一个数字就够了。
列出所有总数，然后选出最大的总数
思路
逐行遍历，将余额相加，并为每位客户保存一个总额：第一个示例中是 [11, 14, 10]。然后扫描这个列表，找出最大值 14。
每个 m × n 余额只会被相加一次，所以时间开销没问题。代价是要创建一个列表，额外保留 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，最后一行的总和为 10 时，它仍保持为 14。
将 richest 初始值设为 0 是安全的，因为余额不会是负数，所以每个总和都至少为 0，全为零的网格会返回 0。如果余额可能是负数，你就应该用第一行的总和作为初始值。
算法
- 将
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
“最富有客户的财富”这道题的时间复杂度是多少？
对于 m 个客户和 n 家银行，时间复杂度为 O(m × n)，因为每个余额都会被加一次。任何算法都不能跳过某个单元格，因为被跳过的余额可能正是让其所有者成为最富有者的那个余额。记录运行过程中的最大值只需要 O(1) 的额外空间。
如何求二维数组中最大的行和？
遍历各行，分别求和，并将最大和保存在一个变量中。许多语言会用内置的 sum 简化内层循环，例如 Python 中的 max(sum(row) for row in accounts)。无论采用哪种方式，每个单元格都只需读取一次。
这些和会超出 32 位整数的范围吗？
这里不会。一行最多有 100 个余额，每个余额最多为 10^4，所以总和最多为 10^6，远小于 2^31 - 1。如果上限更大，你就应该用 64 位整数累加。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def maximumWealth(accounts):
# 在这里编写代码测试 #1
测试 #2
参数
accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
预期输出
14