714 Best Time to Buy and Sell Stock with Transaction Fee

714. Best Time to Buy and Sell Stock with Transaction Fee

1. Question

Your are given an array of integersprices, for which thei-th element is the price of a given stock on dayi; and a non-negative integerfeerepresenting a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

Input:
 prices = [1, 3, 2, 8, 4, 9], fee = 2

Output:
 8

Explanation:
The maximum profit can be achieved by:

The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

0 < prices.length <= 50000.

0 < prices[i] < 50000.

0 <= fee < 50000.

2. Implementation

(1) DP

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];

        buy[0] = -prices[0];
        sell[0] = 0;

        for (int i = 1; i < n; i++) {
            buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee);
        }
        return Math.max(buy[n - 1], sell[n - 1]);
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(n), 空间复杂度O(n)