2019-11-02 12:07:41 +08:00
|
|
|
|
# 63. 股票的最大利润
|
|
|
|
|
|
|
2019-11-03 23:57:08 +08:00
|
|
|
|
## 题目链接
|
|
|
|
|
|
|
|
|
|
|
|
[Leetcode：121. Best Time to Buy and Sell Stock ](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/)
|
2019-11-02 12:07:41 +08:00
|
|
|
|
|
|
|
|
|
|
## 题目描述
|
|
|
|
|
|
|
|
|
|
|
|
可以有一次买入和一次卖出，买入必须在前。求最大收益。
|
|
|
|
|
|
|
2019-12-06 10:11:23 +08:00
|
|
|
|
<div align="center"> <img src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/42661013-750f-420b-b3c1-437e9a11fb65.png" width="220px"> </div><br>
|
2019-11-02 12:07:41 +08:00
|
|
|
|
|
|
|
|
|
|
## 解题思路
|
|
|
|
|
|
|
2020-11-05 01:34:00 +08:00
|
|
|
|
使用贪心策略，假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。因此在遍历数组时记录当前最低的买入价格，并且尝试将每个位置都作为卖出价格，取收益最大的即可。
|
2019-11-02 12:07:41 +08:00
|
|
|
|
|
|
|
|
|
|
```java
|
|
|
|
|
|
public int maxProfit(int[] prices) {
|
|
|
|
|
|
if (prices == null || prices.length == 0)
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
int soFarMin = prices[0];
|
|
|
|
|
|
int maxProfit = 0;
|
|
|
|
|
|
for (int i = 1; i < prices.length; i++) {
|
|
|
|
|
|
soFarMin = Math.min(soFarMin, prices[i]);
|
|
|
|
|
|
maxProfit = Math.max(maxProfit, prices[i] - soFarMin);
|
|
|
|
|
|
}
|
|
|
|
|
|
return maxProfit;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
