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

Problem

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing 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:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

• 0 < prices.length <= 50000.
• 0 < prices[i] < 50000.
• 0 <= fee < 50000.

Problem Summary

Given an integer array prices, where the i-th element represents the stock price on the i-th day; and a non-negative integer fee represents the transaction fee for trading the stock. You may complete an unlimited number of transactions, but you need to pay the fee for each transaction. If you have already bought a stock, you cannot buy again before selling it. Return the maximum profit you can obtain.

Solution Approach

• Given an array representing the price of a stock on each day. Design a trading algorithm to automatically trade on these days, with the following requirements: only one operation can be performed each day; after buying a stock, you must sell it before buying again; after each sale, a transaction fee must be paid. How should you trade to maximize profit?
• This problem is a variant of Problem 121, Problem 122, and Problem 309.
• The solution approach for this problem is DP, where two states, buy and sell, need to be maintained. buy[i] represents the maximum profit from buying on day i, and sell[i] represents the maximum profit from selling on day i. The state transition equations are buy[i] = max(buy[i-1], sell[i-1]-prices[i]), sell[i] = max(sell[i-1], buy[i-1]+prices[i]-fee).

Code

package leetcode

import (
	"math"
)

// Solution 1 Simulated DP
func maxProfit714(prices []int, fee int) int {
	if len(prices) <= 1 {
		return 0
	}
	buy, sell := make([]int, len(prices)), make([]int, len(prices))
	for i := range buy {
		buy[i] = math.MinInt64
	}
	buy[0] = -prices[0]
	for i := 1; i < len(prices); i++ {
		buy[i] = max(buy[i-1], sell[i-1]-prices[i])
		sell[i] = max(sell[i-1], buy[i-1]+prices[i]-fee)
	}
	return sell[len(sell)-1]
}

// Solution 2 DP with optimized auxiliary space
func maxProfit714_1(prices []int, fee int) int {
	sell, buy := 0, -prices[0]
	for i := 1; i < len(prices); i++ {
		sell = max(sell, buy+prices[i]-fee)
		buy = max(buy, sell-prices[i])
	}
	return sell
}