金融软件公司对程序员职位的面试问题
Q1) 假设您有一个数组，其中第 i 个元素是给定股票在第 i 天的价格。
如果您只被允许买入一股股票并卖出一股股票，请设计一种算法来找到买入和卖出的最佳时间。
我的解决方案：我的解决方案是在第 i 天和第 i+1 天之间为 arraysize-1 天制作一个股票价格差异数组，然后使用 Kadane 算法返回最大连续子数组的总和。然后我会在最大连续数组的开始并在最大连续数组的末尾卖出。
我想知道我的解决方案是否正确，还有更好的解决方案吗？？？
回答后，我被问到一个后续问题，我的回答完全相同
Q2) 假设您知道 x 公司未来 10 天的收盘价，请设计一个算法来确定您是否应该每天买入、卖出或持有（您每天只能做出 1 个决定）利润最大化的目标
例如：第 1 天收盘价：2.24
第 2 天收盘价：2.11
...
第 10 天收盘价：3.00
我的解决方案：同上
我想知道是否有更好的算法来最大化利润，因为我每天都可以做出决定
Q1 如果您只被允许买入一股股票并卖出一股股票，请设计一个算法来找到最佳的买入和卖出时间。
在一次遍历数组中，确定i价格最低的索引j和价格最高的索引。你在买入i和卖出j（在买入之前卖出，借入股票，在金融领域通常是允许的，所以如果 是可以的j < i）。如果所有的价格都一样，你什么都不做。
Q2 假设您知道 x 公司未来 10 天的收盘价，请设计一个算法来确定您是否应该每天买入、卖出或持有（您每天只能做出 1 个决定）利润最大化的目标
只有10天，因此只有3^10 = 59049不同的可能性。因此，完全可以使用蛮力。即，尝试每一种可能性，然后简单地选择能够带来最大利润的那个。（即使找到了更有效的算法，这仍然是测试更有效算法的有用方法。）
蛮力方法产生的一些解决方案可能无效，例如，一次拥有（或欠）一份以上的股份是不可能的。此外，您是否需要在 10 天结束时最终拥有 0 只股票，或者是否在 10 天结束时自动平仓？另外，我想澄清一下我在第一季度所做的假设，即可以在买入前卖出以利用股价下跌的机会。最后，可能需要考虑交易费用，包括如果您借入股票以便在购买之前将其出售时需要支付的费用。
一旦澄清了这些假设，就很有可能设计一种更有效的算法。例如，在最简单的情况下，如果您只能拥有一个股票并且您必须在卖出之前买入，那么您将在该系列的第一个最小值处“买入”，在最后一个最大值处“卖出”，然后买入和以介于两者之间的任何最小值和最大值出售。
我想得越多，我就越认为这些面试问题与了解候选人如何以及是否澄清问题一样重要，因为它们是关于问题的解决方案。
以下是一些替代答案：
Q1) 在提供的数组中从左到右工作。跟踪迄今为止看到的最低价格。当您看到数组的一个元素时，记下那里的价格与目前的最低价格之间的差异，更新目前的最低价格，并跟踪看到的最高差异。我的回答是，在以当时最低价格买入后，通过卖出获得最高差额的利润。
Q2）将此视为一个动态规划问题，其中任何时间点的状态都是您是否拥有股份。再次从左到右工作。在每个时间点找到可能的最高利润，假设在该时间点结束时拥有股份，并且假设您在该时间点结束时不拥有股份。您可以从上一个时间步的计算结果中得出这个结论：在一种情况下，比较购买股票的选项，并从利润中减去这个选项，因为您在上一个时间点结束时没有拥有或持有股票你在前一点拥有的。在另一种情况下，比较出售股票以增加您之前拥有的利润的选择，或者考虑到您之前不拥有的利润保持不变。
您对第一个问题的解决方案是正确的。Kadane 算法的运行时间复杂度为O(n)，是最大子数组问题的最优解。使用该算法的好处是易于实现。
根据我的说法，您对第二个问题的解决方案是错误的。您可以做的是存储您找到的最大和子数组的左右索引。一旦找到最大和子数组及其左右索引。您可以在左侧再次调用此函数，即 0 到左 -1 和右侧，即右 + 1 到 Array.size - 1。因此，这基本上是一个递归过程，您可以进一步设计此递归的结构基本案例来解决这个问题。通过遵循这个过程，您可以最大化利润。
您对问题 1 的回答是正确的。
您对问题 2 的回答不正确。要解决这个问题，您需要从头开始，在每一步中选择最佳选项。例如，给定序列 { 1, 3, 5, 4, 6 }，由于 4 < 6，您的最后一步是卖出。由于 5 > 4，上一步是买入。由于 3 < 5，因此 5 的移动是卖出。以同样的方式继续，3 的动作是持有，1 的动作是买入。
假设价格是数组P = [p_1, p_2, ..., p_n]
构造一个新数组A = [p_1, p_2 - p_1, p_3 - p_2, ..., p_n - p_{n-1}]
即A[i] = p_{i+1} - p_i，服用p_0 = 0.
现在去寻找这个中的最大和子数组。
或者
寻找不同的算法，解决最大子数组问题！
问题是等价的。