题目链接
题目描述
实现代码
思路:本题主要是让我们选择股票买卖的两个时机,我们假设买股票是cur_buy,卖股票是在cur_sale,可以知道:
- cur_buy 在 cur_sale之前;
- cur_buy 小于 cur_sale;
同时进一步的思考可以知道:
- cur_buy可能是从开始遍历找到第一个最后递减的值,cur_buy则可能是从cur_buy下一个位置开始遍历找到第一个最后递增的值;这两者的差值可能是最终结果;
- 为什么说是可能,因为可能在cur_sale之后还是会存在这样的组合,结果比他们更大;
因此,我们需要维护这两个值,同时维护一个ans大值结果,经过一轮遍历找到所有这样的组合,同时只记录最大的ans,最终的ans即为结果
实现代码如下:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 1:
return 0
cur_buy = prices[0]
cur_sale = -1
ans = 0
first = True
for price in prices:
if first:
first = False
continue
if price < cur_buy:
cur_buy = price
if cur_sale == -1:
continue
cur_sale = -1
continue
if price > cur_sale:
cur_sale = price
ans = max(cur_sale - cur_buy, ans)
continue
return ans
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}