"买卖问题"是一个经典的优化问题。可以这样描述：
有$n$城市。对于每个城市，给出该城市的产品价格(正数(。现在一个人将一个接一个地从城市 1 旅行到城市 $n$。到达一个城市时，他可以只购买一种与该城市价格相同的产品，或者如果他目前至少拥有一种产品，则可以只出售一种产品。他也可以什么都不做，然后继续前往下一个城市。问题是如何计划一个策略，以便他能够赚到最大的钱。
这个问题有一个正确的贪婪算法。到达城市 $i $ 时，请考虑所有 $j$ 在 1 美元中......i-1$，并找到一个价格最低的$j$，这样他就不会在城市$j$购买产品(他本可以在城市$j$出售产品(。然后他在城市$j$购买产品，并在城市$i$出售。该算法以递增的顺序运行所有$i$，最后给出最佳策略。
解决方案很简单，但如何证明其正确性？
好的，所以证明不会很正式，但我希望这就足够了。
让我们考虑城市 i，在那里您可以以 x 的价格购买/出售产品。您想在那里出售比x便宜的产品以赚钱。所以你想找到以前城市最便宜的产品，价格低于x，而你还没有买。假设它的成本是y。如果我们在这里出售它，我们就会赚(x - y(。
现在我们去下一个城市，j。如果您可以在这里以超过 x 的价格出售该产品，比如说 z，该怎么办？然后你会赚 (z - y(，它比 (x - y(...那么你是否做出了错误的决定？
假设他可以在一个城市购买和销售产品。然后，你的决定实际上并不重要。如果您在城市 i 销售产品，即 x，您将立即获得 (x - y(。然后，您还可以在城市i购买产品，这将花费您x钱。现在，当你到达城市j时，你可以以价格(z - x(出售它。这样做总共能赚多少钱？完全：
x - y + z - x = z - y
这等于用y买一个产品，然后在城市j卖给z。
我们可以很容易地看到，在一个城市销售和购买产品给我们的结果与根本不在该城市销售产品的结果完全相同。那么，是否可以同时买卖有关系吗？不，不是真的。就像根本不在那里卖一样。我们可以通过在 i 中购买另一种产品来拒绝在城市 i 销售产品。
如果 z 实际上小于 x 怎么办？如果是这样，你已经做出了一个伟大的决定，以z而不是x的价格销售产品会给你更少的东西。
无论j的价格是多少，您都做出了在城市i销售产品的良好决定。所以你的算法总是做出最好的选择，这就是它工作的原因。