Best time to Buy and Sell stock modified version

Question

Say you have an array for which the ith element is the price of a given stock on day i.

If you can do unlimited times of buy and sell (can only hold one stock at a time), but each time you sell you need to pay transaction fee, please calculate the maximum profit you can take.

Sample input { 1, 3, 7, 5, 10, 3 } fee = 3.

If you do two transactions, the total profit is (7 - 1) - 3 + (10 - 5) - 3 = 5. If you only to one transaction, the total profit is (10 - 1) - 3 = 6.

public int maxProfit(int[] prices, int fee) {}

The original version is pretty straightforward but I'm not sure how to approach this modified version. Can anyone give me some hints/guidance? I'm studying algorithm problems for interviews.

Answer 1

This problem can be solved by applying Dynamic programming technique.

Let's form a recursive formula for this problem.

Starting from the first day, we will iterate through the last day. For each day, there are two cases which we will need to make decision:

• Either we have one stock in our hand, and we need to decide whether we hold it till the next day, or we sell it and get some profit
• Or we don't have any stock and we need to decide whether we will buy one or wait till the next day.

So, here is the formula, let's say we are at 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 see that, the problem can be represented by using two variables, current_day and have_stock => we can use a simple dp[n][2] table to store the result. Time complexity will be O(n)

Answer 2

Imagine you can see into 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 the transaction fees! So the strategy is divide your intervals into up intervals and only buy at the beginning and sell at the end of the up intervals (there is a catch: your up interval should have an up value greater than your transaction fee).

Example:

[10, 1, 14, 18, 21, 5, 7, 10, 31, 4, 11]

There are three up intervals [1, 14, 18, 21], [5, 7, 10, 31], [4, 11].

--

Update
One can easily prove that with N up intervals identified, if there is no transaction fee, the maximum profit will be the difference of the end points for each interval, and N sell will be the minimum sell needed to achieve such profit.

Therefore there will be no solution that is greater than N that have better profits

However, it is possible that there will be k = N-n sells ( 0< n < N-1) solutions that have better profits. Therefore for at 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];
}

Answer 3

I wanted to try a different answer that just iterates and scans ahead. I think is linear in time and space complexity. I don't know Java but here is a python version. It calculates pairs of (buy_date, sell_date) for when purchases are made, 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))

Answer 4

In each day, you have two status: hold the current stock or empty which means you don't have any stock. So you can use two arrays to achieve a DP solution:

The time complexity is O(n) and the 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];
    }

Answer 5

Here's a non-recursive O(1) space, O(N) time solution in C++ which does not 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;
}