买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释:
在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。示例 2:
输入: [1,2,3,4,5]
输出: 4
解释:
在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3:
输入: [7,6,4,3,1]
输出: 0
解释:
在这种情况下, 没有交易完成, 所以最大利润为 0。初步解答¶
初步看了题目之后，首先想到的是，寻找一个数组中的最小值，然后从该最小值下标的右数组再找最大值，两者相减就是收益，然后再将最大值下标的右数组重复操作，得到结果。
In [1]:
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
length = len(prices)
if length <= 1:
return 0
min_price = min(prices)
min_index = prices.index(min_price)
left_prices = prices[min_index:]
max_price = max(left_prices)
max_index = left_prices.index(max_price) + min_index
benefit = max_price - min_price
if max_index < length:
benefit += Solution().maxProfit(prices[max_index:])
return benefit
In [2]:
a = [7,1,5,3,6,4]
Solution().maxProfit(a)
Out[2]:
但是很可惜，这个结果和题目给出的结果不符。
第二次解答¶
再次审题之后发现，题目是要求求一个数组的最大收益。所以应当思考在何种方式下求出最大收益。
通过对题目数组，我们可以计算两天收益的相邻之差，得到一个新数组。这样就将问题转化，求该数组的累计和。
In [3]:
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
length = len(prices)
if length <= 1:
return 0
benefits = []
i = 1
while i < length:
benefit = prices[i] - prices[i-1]
benefits.append( benefit if benefit > 0 else 0 )
i+=1
return sum(benefits)
提交到LeetCode上测试通过。emmm 算法是没什么问题了，但是执行时间是属于比较 low 的那一档。
接下来继续进行优化。
优化¶
优化思路：
- 首先我们无需需要一个数组来存储邻接差，只需要创建一个数值来累加就好，这样就节省了一个函数调用（sum）和数组空间。
- 其次，我们的思路是 邻接差 大于0 才累加，否则为0 。则我们可以判断 下一个值是否大于上一个值， 这样就节省一个三元表达式的判断。这里需要值得注意的是，我们需要用本地变量来保存两个值。
以下是他们之间的执行时间，可以看到，这次修改会给我们带来 25% 的性能提升。
original
2.06 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)第一次修改
1.54 µs ± 4.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)修改之后的代码如下:
In [4]:
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
length = len(prices)
if length <= 1:
return 0
benefits = 0
i = 1
while i < length:
second = prices[i]
first = prices[i-1]
if second - first > 0:
benefits += second - first
i+=1
return benefits
提交上去之后，发现执行用例大约在60ms。再参考一下第一名 40ms 的答案。
In [5]:
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
profit = 0
for i in range(1,len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i]-prices[i-1]
return profit
In [6]:
%timeit Solution().maxProfit(a)
发现差距并没有想象中的大，至此解答就到这里。
In [7]:
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
length = len(prices)
if length <= 1:
return 0, [0] * length
benefits = 0
operations = {0: 0}
i = 1
while i < length:
second = prices[i]
first = prices[i-1]
if second - first > 0:
benefits += second - first
operations[i-1] = 1
operations[i] = 2
else:
operations[i] = 0
i+=1
return benefits, list(operations.values())
In [8]:
Solution().maxProfit(a)
Out[8]:
Comments !