买卖股票的最佳时机及其变形

1 题1：面试题1.1 问题1思路1.2 问题1代码实现1.3 问题2思路1.4 问题2代码实现 2 题2：只能完成一笔交易2.1 思路1：暴力解法2.2 思路2：一次遍历 3 题3：能完成多笔交易3.1 思路 4 参考

1 题1：面试题

给定一个数字v代表开始有多少钱，一个数组代表股票每天的价格。

Q1：请问最多只能买一次、卖一次的情况下，最大化利润是多少？Q2：不限制买卖次数的情况下，利润可以达到多少呢？

样例：

输入：1000

[100,80,120,130,70,60,100,125]

输出： Q1输出：1040Q2输出：2290

1.1 问题1思路

首先这个买入卖出是有时间顺序的！所以不能出现最后一天买入，第一天卖出的情况，这是不符合实际情况一开始有多少钱，买股票的时候需要考虑多少手！然后再结合具体每天股票每手的价格具体思路一开始可以首先考虑暴力解法，然后再进行优化！

1.2 问题1代码实现

整除 100 // 3 33 取余 100 % 3 1 v = 1000 a = [100,80,120,130,70,60,100,125] profit = [] for i in range(len(a)-1): p1 = a[i] p2 = max(a[i+1:]) p_ = 1000 // p1 * p2 - 1000 + (1000%p1) profit.append(p_) p_max = max(profit) p_max 1040

1.3 问题2思路

也是反过来看！即如果后比前价格高，那么就可以进行买卖！否则继续往前进，不买卖！

1.4 问题2代码实现

def get_profit_max_v(a): ''' a：每天股票价格的list ''' profit = [] # 初始利润 p = 0 pos_end = len(a)-1 pos_start = pos_end - 1 while pos_start >= 0: print(pos_start) opt = 0 while a[pos_start] < a[pos_end]: pos_start -= 1 pos_end -= 1 opt += 1 print(opt) if opt == 0: # 表明无法发生获利行为 pos_end = pos_start pos_start = pos_end - 1 else: # 表明可以发生获利行为 print(a[pos_start+1]) print('*****') print(a[pos_end+opt]) p_ = 1000 // a[pos_start+1] * a[pos_end+opt] - 1000 + (1000 % a[pos_start]) print(p_) profit.append(p_) pos_end = pos_start pos_start = pos_end - 1 return sum(profit) a = [100,80,120,130,70,60,100,125] get_profit_max_v(a) 6 2 60 ***** 125 1020 3 0 2 2 80 ***** 130 560 1580

但是结果和上述样例给出来的不一致，还有待继续思考！

2 题2：只能完成一笔交易

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

输入: [7,1,5,3,6,4]

输出: 5

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

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

2.1 思路1：暴力解法

def get_max_pro_once(a): profit = [] for i in range(len(a)-1): p1 = a[i] p2 = max(a[i+1:]) p_ = p2-p1 if p_ < 0 : profit.append(0) else: profit.append(p_) return max(profit) a = [7,1,5,3,6,4] get_max_pro_once(a) 5 a = [7,6,4,3,1] get_max_pro_once(a) 0

2.2 思路2：一次遍历

即一开始先定义一个最小min【inf】和最大利润Max【0】，然后遍历列表的所有元素：

如果小于最小值，则赋值该值为min

如果当前价格减去最小min的利润大于Max，则赋值给max

表示最大值

a = float('inf') 9999 < a True 表示最小值 a = float('-inf') -9999 > a True def get_max_pro_one(a): min_p = float('inf') max_pro = 0 for p in a: if p < min_p: # 如果当前价格都小于最小的价格 那肯定是不能卖的！亏本了！ min_p = p elif p - min_p > max_pro: max_pro = p - min_p return max_pro a = [7,1,5,3,6,4] get_max_pro_one(a) 5 a = [7,6,4,3,1] get_max_pro_one(a) 0

3 题3：能完成多笔交易

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

输入: [1,2,3,4,5]

输出: 4

解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

3.1 思路

直接反过来考虑，然后遇到比它小的元素则继续，否则停止！两个指针！

def get_profit_max(a): ''' a：每天股票价格的list ''' profit = [] # 初始利润 p = 0 for i in range(len(a)-1,-1,-1): # 后一个元素 p1 = a[i] # 前一个元素 p2 = a[i-1] if p1 < p2: profit.append(p) continue else: # 表示价格是上升的 有获利空间 p += (p1 - p2) return max(profit) a = [7,1,5,3,6,4] get_profit_max(a) 7 a = [1,2,3,4,5] get_profit_max(a) 4 a = [7,6,4,3,1] get_profit_max(a) 0

4 参考

https://blog.csdn.net/qq_45556599/article/details/104543562总结的特别好的：https://blog.csdn.net/qq_36512295/article/details/100761888