admin管理员组文章数量:1530263
Suppose that you have been offered the opportunity to invest in the Volatile Chemical Corporation. Like the chemicals the company produces, the stock price of the Volatile Chemical Corporation is rather volatile. You are allowed to buy one unit of stock only one time and then sell it at a later date, buying and selling after the close of trading for the day. To compensate for this restriction, you are allowed to learn what the price of the stock will be in the future. Your goal is to maximize your profit.
The problem 1: you are allowed to complete transaction only once, how do you calculate the max profit you may get?
def max_profit_1(prices):
max_profit = 0
n = len(prices)
if n > 1:
min_price = prices[0]
i = 1
while i < n:
if prices[i] > min_price:
profit = prices[i] - min_price
if profit > max_profit:
max_profit = profit
else:
if min_price > prices[i]:
min_price = prices[i]
i += 1
return max_profit
The problem 2: you are allowed to complete at most two transactions, how do you calculate the max profit you may get?
(Note: you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again)).
def max_profit_2(prices):
max_profit = 0
n = len(prices)
if n > 1:
left = [0 for i in range(n)]
right = [0 for i in range(n)]
min_price = prices[0]
i = 1
while i < n:
if prices[i] > min_price:
profit = prices[i] - min_price
if profit > max_profit:
max_profit = profit
else:
min_price = prices[i]
left[i] = max_profit
i += 1
max_profit = 0
i = n - 2
max_price = prices[n - 1]
while i >= 0:
if prices[i] < max_price:
profit = max_price - prices[i]
if max_profit < profit:
max_profit = profit
else:
max_price = prices[i]
right[i] = max_profit
i -= 1
i = 1
max_profit = left[n - 1]
while i < n - 2:
profit = left[i] + right[i + 1]
if profit > max_profit:
max_profit = profit
i += 1
return max_profitThe problem 3: you are allowed to complete transactions at most k (>2) times, how do you calculate the max profit you may get?
(Note: you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again)).
def max_profit_matrix(prices):
n = len(prices)
assert n > 1
ret = [[0 for i in range(n)] for j in range(n - 1)]
for i in range(n - 1):
min_price = prices[i]
max_profit = 0
j = i + 1
while j < n:
if prices[j] > min_price:
profit = prices[j] - min_price
if profit > max_profit:
max_profit = profit
else:
min_price = prices[j]
ret[i][j] = max_profit
j += 1
return ret
def max_profit_k(prices, k):
assert k > 2
max_profit = 0
n = len(prices)
if n > 1:
M = max_profit_matrix(prices)
cache = [[0 for i in range(n + 1)] for j in range(2)]
max_price = prices[n - 1]
max_profit = 0
i = n - 2
while i >= 0:
if prices[i] < max_price:
profit = max_price - prices[i]
if profit > max_profit:
max_profit = profit
else:
max_price = prices[i]
cache[0][i] = max_profit
i -= 1
prev = 0
curr = 1
r = 2
while r <= k:
for i in range(n - 1):
j = i + 1
max_profit = cache[prev][i]
while j < n:
profit = M[i][j] + cache[prev][j + 1]
if profit > max_profit:
max_profit = profit
j += 1
cache[curr][i] = max_profit
prev = curr
curr = ((curr + 1) & 1)
r += 1
max_profit = cache[prev][0]
return max_profit
The test code:
if __name__ == "__main__":
prices = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
assert max_profit_1(prices) == 43
assert max_profit_2(prices) == 63
assert max_profit_k(prices, 3) == 81
assert max_profit_k(prices, 4) == 94
版权声明：本文标题：The Maximum-Subarray Problem 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1725146764a1009440.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论