Amazon 面试真题解析：Walmart 买入 Amazon 卖出最大利润

Question:

Sellers buy items in Walmart during sale events and sell them on Amazon to make money. You have to help a seller make maximum profit for their purchase.

You are given two lists, one for Walmart price and another for Amazon price of an item over a period of time. The ith entry in both lists is the price of the item at time i in Walmart and Amazon.

Example:

Walmart: 4, 7, 5, 8
Amazon:  6, 8, 7, 8

Answer: 4

Seller can buy the item at 0th time index from Walmart at $4 and sell at Amazon on 1st time index at $8, making a profit of $4.

这道题的核心是找出一个最优买卖时机：在 Walmart 的价格序列中选择某个时刻买入，再在 Amazon 的价格序列中选择更晚的时刻卖出，使得卖出价减去买入价最大。样例中 Walmart 为 4, 7, 5, 8，Amazon 为 6, 8, 7, 8，因此最佳方案是第 0 个时刻以 4 买入、第 1 个时刻以 8 卖出，最大利润为 4。实现时可以用一次遍历维护历史最低买入价，并在遍历 Amazon 时持续更新最大差值，时间复杂度可做到线性。