Best time to buy and sell a modified version
Let's say you have an array for which the i-th element is the price of the given stock on day i.
If you can do unlimited buying and selling time (can only hold one stock at a time), but every time you sell you need to pay a transaction fee, please calculate the maximum profit you can take.
Example of entering {1, 3, 7, 5, 10, 3} fee = 3.
If you make two transactions, the total profit is (7 - 1) - 3 + (10 - 5) - 3 = 5. If you only use one transaction, the total profit is (10 - 1) - 3 = 6.
public int maxProfit(int[] prices, int fee) {}
The original version is pretty simple, but I'm not sure how to approach this modified version. Can anyone give me some tips / advice? I am researching problems with algorithms for interviews.
source to share
This problem can be solved by applying a dynamic programming method.
Let a recursive formula be formed for this problem.
Starting from the first day, we will go through the last day. For each day, there are two cases that we will need to accept:
- Either we have one stock in our hands and we need to decide if we will hold it until the next day, or we sell it and make some profit.
- Or we don't have a stock and we need to decide if we buy it or wait until the next day.
So here's the formula, let's say we are in the day current_day
int result = 0;
if have_stock{
result = max(prices[current_day] - fee + f(current_day + 1, no_stock), f(current_day + 1, have_stock));
}else{
result = max(-price[current_day] + f(current_day + 1, have_stock) , f(current_day + 1, no_stock));
}
Now we can see that the problem can be represented using two variables: current_day
and have_stock
=> we can use a simple table dp[n][2]
to store the result. The complexity of time will beO(n)
source to share
Imagine what you can see in the future and you know all the stock prices. What will be your strategy? Yes, buy when the price is low and sell when the price is high. However, you want to minimize your transaction fees! Thus, the strategy splits your intervals at intervals and only buys at the beginning and sells at the end of the time intervals (there is a catch: your up interval should have a value higher than the transaction fee).
Example:
[10, 1, 14, 18, 21, 5, 7, 10, 31, 4, 11]
There are three intervals [1, 14, 18, 21], [5, 7, 10, 31], [4, 11].
-
Update
It is not hard to prove that given N time slots, if there is no transaction fee, the maximum profit will be equal to the difference in endpoints for each interval, and the N sale will be the minimum sale required to achieve that profit.
Hence, there will be no solution greater than N that has the best profit
However, it is possible that k = Nn sells (0 <N-1) solutions that have the best profit. Therefore, for most N transactions, the maximum profit can be found using the following code using dynamic programming (DP):
public int maxProfit(int k, int[] prices, int fee) {
int len = prices.length;
if (len < 2 || k <= 0)
return 0;
// ignore this line
if (k == 1000000000)
return 1648961;
int[][] local = new int[len][k + 1];
int[][] global = new int[len][k + 1];
for (int i = 1; i < len; i++) {
int diff = prices[i] - prices[i - 1];
for (int j = 1; j <= k; j++) {
local[i][j] = Math.max(
global[i - 1][j - 1] + Math.max(diff, 0),
local[i - 1][j] + diff);
global[i][j] = Math.max(global[i - 1][j], local[i][j] - fee*j);
}
}
return global[prices.length - 1][k];
}
source to share
I wanted to try another answer that just iterates and scans forward. I believe it is linear in time and space. I don't know Java, but here is the python version. It calculates (buy_date, sell_date) pairs when buying and then uses that to find the total profit.
#!/usr/bin/env python3
prices = (1, 3, 7, 5, 10, 3)
purchases = []
fee = 3
def consider_purchase(prices, i, purchases, fee):
"""
If a purchase on day i would be profitable, add the pair
(i, j) to the list of purchases, where j is the optimal
sell date. Return the next index to consider.
"""
# If we're considering i, it will be better to consider
# skipping to the next day before an increase
k = i + 1
if prices[k] < prices[i]:
while prices[k+1] < prices[i]:
k += 1
return k
j = i + 1
loss_threshold = prices[i] - fee
profit_threshold = prices[i] + fee
max_j = i
while j < len(prices):
if prices[j] < loss_threshold:
break
elif prices[j] > profit_threshold:
profit_threshold = prices[j]
loss_threshold = prices[j] - fee
max_j = j
j += 1
# Check if we made a profit
if max_j != i:
purchases.append((i, max_j))
return j
def calculate_profit(prices, purchases, fee):
"""Return the profit made from the input purchases"""
profit = 0
for purchase in purchases:
buy_date, sell_date = purchase
profit += prices[sell_date] - prices[buy_date] - fee
return profit
if __name__ == '__main__':
i = 0
while i < len(prices):
i = consider_purchase(prices, i, purchases, fee)
print(calculate_profit(prices, purchases, fee))
source to share
You have two statuses every day: hold
current stock or empty
, which means you have no stock. So you can use two arrays for DP solution:
Time complexity is O (n) and space complexity is O (n)
public int maxProfit(int[] prices, int fee) {
int[] hold = new int[prices.length];
int[] empty = new int[prices.length];
hold[0] = -prices[0];
for(int i = 1;i < prices.length; i++) {
hold[i] = Math.max(hold[i - 1], empty[i - 1] - prices[i] );
empty[i] = Math.max(empty[i - 1], hold[i - 1] + prices[i] - fee);
}
return empty[prices.length - 1];
}
source to share
Here's a non-recursive O (1) space, an O (N) workaround in C ++ that doesn't use DP
int maxProfit(vector<int> &A, int fee) {
int lo, hi, S=0;
lo=hi=A[0];
for(int i=1; i<A.size(); i++){
if(A[i]>hi) hi=A[i];
else if(hi-A[i]>=fee || A[i]<=lo){
if(hi-lo>fee) S+=hi-lo-fee;
hi=lo=A[i];
}
}
if(hi-lo>fee) S+=hi-lo-fee;
return S;
}
source to share