This is a question derived from the problem of returning the maximum profit from a list of prices through k number of transactions. I would like to not just return the profit but a list with the transactions that result in the maximum profit. For example, if the list of prices is [1, 5, 2, 3, 7, 6, 4, 5] and the k number of transactions allowed is k, the maximum profit is 10, but I would like to return a list like [(1, 5), (2, 7), (4, 5)], where the first values is the buying price and the second value is the selling price.
I have the following function, also have two variables outside of the function that I've set as global inside the function in order to return the complete lists of profits and transactions that are possible
profit_list = []
transaction_list = []
def findMaxProfit(price, k):
global profit_list
global transaction_list
# get the number of days `n`
n = len(price)
# base case
if n <= 1:
return 0
# profit[i][j] stores the maximum profit gained by doing
# at most `i` transactions till j'th day
profit = [[0 for x in range(n)] for y in range(k + 1)]
# transactions[i][j] stores the buying price and sell price
transactions = [[(0,0) for x in range(n)] for y in range(k + 1)]
# fill profit[][] in a bottom-up fashion
for i in range(k + 1):
for j in range(n):
# profit is 0 when
# i = 0, i.e., for 0th day
# j = 0, i.e., no transaction is being performed
if i == 0 or j == 0:
profit[i][j] = 0
else:
max_so_far = 0
for x in range(j):
curr_price = price[j] - price[x] + profit[i-1][x]
if max_so_far < curr_price:
max_so_far = curr_price
transactions[i][j] = (price[x],price[j])
profit[i][j] = max(profit[i][j-1], max_so_far)
profit_list = profit
transaction_list = transactions
return profit[k][n-1]
if prices = [1, 5, 2, 3, 7, 6, 4, 5] and k = 3 for example, the function works in returning the maximum profit (in this case 10) and the transactions that are possible given the transaction_list variable are the following
[[(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
[(0, 0), (1, 5), (1, 2), (1, 3), (1, 7), (1, 6), (1, 4), (1, 5)],
[(0, 0), (1, 5), (1, 2), (2, 3), (2, 7), (2, 6), (2, 4), (2, 5)],
[(0, 0), (1, 5), (1, 2), (2, 3), (2, 7), (2, 6), (6, 4), (4, 5)]]
What change to the function or manipulation of the transaction list could I employ in order to obtain the transaction list that leads to the maximum profit?
It's a lot easier if you solve this using recursion.
Every day you can either trade or hold. Work out how much profit you would make in either case, and then recurse over the remaining days in the price history to see how the decision plays out. Choose whichever option (trade or hold) yielded the greater profit.
Keep track of the transactions by returning a tuple containing the profit made and the transaction history.
Something like this:
def findMaxProfit(price_history, k, stock_value=None, profit=0, transactions=[]):
"""
Find the maximum profit available from k transactions in the given
price history.
stock_value: the price paid for stock currently held.
profit: the amount of profit accumulated by trading so far.
transactions: a list of transactions (buying_price, selling_price).
"""
if len(price_history) == 0:
# Base case, no more history.
return (profit, transactions)
# Destructure to get today's price and the remaining price history.
todays_price, *remaining_history = price_history
# Find the maximum profit that can be achieved on the basis that we
# do not trade today.
hold_profit, hold_transactions = findMaxProfit(
remaining_history,
k,
stock_value,
profit,
transactions)
# Find the maximum profit that can be achieved on the basis that we trade.
# We either sell stock we already have or buy stock.
if stock_value != None:
# We have stock, so we sell it. We add the sales revenue into our
# profit accumulator and update the list of transactions.
sales_revenue = todays_price - stock_value
updated_profit = profit + stock_value + sales_revenue
updated_transactions = transactions + [(stock_value, todays_price)]
trade_profit, trade_transactions = findMaxProfit(
remaining_history,
k,
None,
updated_profit,
updated_transactions)
elif k > 0:
# We don't have any stock. We can buy stock as long as we are
# within the transaction limit. We buy stock at today's price. It's
# not a transaction until we sell, so no need to update the list.
updated_profit = profit - todays_price
trade_profit, trade_transactions = findMaxProfit(
remaining_history,
k - 1,
todays_price,
updated_profit,
transactions)
else:
# If we can't do anything then that's the same as holding.
trade_profit = hold_profit
trade_transactions = hold_transactions
# Return whichever worked
if hold_profit >= trade_profit:
# We make more profit by holding.
return hold_profit, hold_transactions
else:
# We make more profit by trading.
return trade_profit, trade_transactions
prices = [1, 5, 2, 3, 7, 6, 4, 5]
k = 3
profit, transactions = findMaxProfit(prices, k)
print(profit, transactions)
Gives:
10 [(1, 5), (2, 7), (4, 5)]