C++面试宝典第22题：买卖股票的最佳时机_买卖股票的最好时机c++语言

题目

        给定一个整型数组，它的第i个元素是一支给定股票第i天的价格。如果最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。

        示例 1：

输入: [7, 1, 5, 3, 6, 4]
输出: 5
 
解释: 在第2天（股票价格=1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润为6-1=5。
注意：利润不能是7-1=6, 因为卖出价格需要大于买入价格；同时，不能在买入前卖出股票。

        示例 2：

输入: [7, 6, 4, 3, 1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为0。

解析

        这道题比较贴合实际，主要考察应聘者对暴力法、贪心算法、动态规划算法等的理解和掌握。

        首先，我们使用暴力法来求解本题。暴力法需要遍历数组两遍，故时间复杂度为O(n^2)。我们可以用变量i表示买入股票的索引，用变量j表示卖出股票的索引，那么prices[j] - prices[i]就是股票收益，我们找出最大的即可。具体的实现，可以参考下面的示例代码。