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.

Examples

Example 1:

1
2
3
4

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Solution

Method 1 - Handling the states

Here is the approach:

  1. Cash and Hold States:
    • cash represents the maximum profit we can have if we do not own a stock on the i-th day.
    • hold represents the maximum profit we can have if we own a stock on the i-th day.
  2. Transition between states:
    • When selling a stock: cash = max(cash, hold + prices[i] - fee)
    • When buying a stock: hold = max(hold, cash - prices[i])

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int cash = 0, hold = -prices[0]; // Initialize cash and hold states

        for (int i = 1; i < n; i++) {
            cash = Math.max(cash, hold + prices[i] - fee); // Selling stock
            hold = Math.max(hold, cash - prices[i]); // Buying stock
        }

        return cash;
    }
}
1
2
3
4
5
6
7
8
9

def maxProfit(prices, fee):
    n = len(prices)
    cash, hold = 0, -prices[0]  # Initialize cash and hold states

    for i in range(1, n):
        cash = max(cash, hold + prices[i] - fee)  # Selling stock
        hold = max(hold, cash - prices[i])  # Buying stock

    return cash