题目

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

示例

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

解答

方法一

贪心:如果我是在历史最低点买进的,那么我今天卖出能赚多少钱?当考虑完所有天数之时,我们就得到了最好的答案。

然后动态规划,定义状态和转移方程。

考虑卖出的操作,在第 i 天时:

  • 卖出,此时最大利润即当前股价减去之前买入的最低价;
  • 不卖,最大利润没发生变化,仍是第 i-1 天 的最大利润。

取两者较大值即为前 i 天的最大利润。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int maxProfit(vector<int>& prices) {
int inmin=INT_MAX; // 在今天之前的股票价格最低点
int res=0;
for(auto price : prices){
res = max(res,price-inmin); // 如果在今天卖出,最大的利润
inmin = min(inmin, price); // 更新股价最低点
}
return res;
}
};

复杂度

  • 时间复杂度 O(n)
  • 空间复杂度 O(1)