股票买卖问题

问题介绍

给定一个名为 prices 的数组，其中第 i^th 个索引存储了股票在第 i^th 天的价格。

这个问题涉及确定买卖股票的最佳时机，以实现利润最大化。

这个问题在亚马逊、微软、DE Shaw、Paytm、谷歌、沃尔玛等公司的软件开发工程师（SDE）面试中被问到过。

示例 1

示例 2

目标是找到我们通过在此期间买卖股票可以获得的最大可能利润。

但是，需要遵守一些限制条件：

• 每天一次交易 - 在某一天，我们只能买入或卖出股票。
• 一次持有一只股票 - 我们一次只能持有一只股票。在购买另一只股票之前，我们必须卖掉当前的股票。

问题 - 找到最大利润

通常，我们只会被要求找到最大利润。在这种情况下，我们可以使用简单的贪心算法。

• 初始化利润 profit = 0。
• 从 i = 1 遍历到 prices 列表的末尾 (n-1)
• 检查当前价格 (prices[i]) 是否高于前一天的价格 (prices[i-1])
• 利润 = 利润 + 当前价格 (prices[i]) - 前一天价格 (prices[i-1])
• 遍历完所有价格后，返回赚取的总利润。

Python 代码

输出

C++ 代码

输出

C 代码

输出

问题 - 找到买卖股票以最大化利润的最佳日期。

这个问题比仅找到利润要复杂一些。在这个问题中，我们被要求找到可以买卖股票以产生最大利润的日期区间。

以上面讨论的第一个例子为例

在这个问题中，我们将返回一个包含日期区间的列表，[(0, 3), (4, 5)]，在这些区间内我们可以买卖股票。

这个问题可以通过确定局部最大值和局部最小值之间的差异并累加利润来解决。

特殊情况

• 当价格以非递增顺序存储时，利润将为零。
• 当所有天的价格保持不变时，利润将为零。

该算法可总结如下：

• 从头到尾遍历价格列表。
• 找到局部最小值和局部最大值的索引。
• 将它们存储为一对。这些对表示可以在这些日期区间之间产生利润。
• 重复这个过程，直到我们遍历完所有价格。

Python 代码

输出

说明

在上面的程序中，我们使用 while 循环遍历所有价格。我们首先找到局部最小值的索引并将其存储在 buy_on 变量中。

然后我们搜索局部最大值，如果找到，我们将其存储在 sell_on 变量中。

然后我们将 buy_on 和 sell_on 存储在 segments_of_days 列表中。在找到所有可能的区间后，我们返回答案。

C++ 代码

输出

C 代码

输出

注意 - C 代码分别使用 realloc() 和 free() 函数对动态区间数组进行内存分配和释放。

结论

股票买卖的编程问题通常使用各种算法来解决，如暴力法、动态规划和贪心算法。最佳解决方案取决于手头问题的具体要求和约束。

贪心算法被用来解决这两种变体。

在第一种变体中，我们遍历价格，并在当前价格较高时，通过计算当前价格与前一天价格的差值来计算利润。

在第二种变体中，我们找到应该买入和卖出股票以产生最大利润的日期区间。

总的来说，股票买卖问题是各大公司面试中常见的算法问题，可以使用贪心算法高效解决。