Introduction

In this problem, you are given an array arr[] where each element represents the stock price on a particular day, and an integer k representing the transaction fee.

You are allowed to:

The goal is to maximize total profit.

Key Idea

Instead of tracking every transaction explicitly, we use Dynamic Programming with two states:

Two States

1. HOLD state

Code
hold = max(hold, cash - price)

2. CASH state

Code
cash = max(cash, hold + price - k)

State Transitions

For each price:

Sell decision:

Buy decision:

Step-by-Step Approach

Step 1: Initialization

Step 2: Traverse prices

For each day:

Step 3: Return result

Example

Input:

Code
arr = [6, 1, 7, 2, 8, 4], k = 2

Step-by-step transactions:

Final Profit:

Code
8

Java Code

Code
class Solution {
    public int maxProfit(int arr[], int k) {

        int hold = -arr[0]; // buy first stock
        int cash = 0;       // no stock in hand

        for (int i = 1; i < arr.length; i++) {

            int prevCash = cash;

            // Sell stock
            cash = Math.max(cash, hold + arr[i] - k);

            // Buy stock
            hold = Math.max(hold, prevCash - arr[i]);
        }

        return cash;
    }
}

Output Example

Input:

Code
arr = [6, 1, 7, 2, 8, 4], k = 2

Output:

Code
8

Complexity

Conclusion

This problem demonstrates a powerful Dynamic Programming state transition approach.

Instead of tracking all buy/sell combinations, we simplify the problem into two states:

The transaction fee is applied during selling, ensuring correct profit calculation.

This technique is widely used in stock trading DP problems and helps reduce complexity from exponential to linear time.

Key Takeaway

Think in states, not transactions.

Summary

This article explains how to maximize stock trading profit with a transaction fee using a dynamic programming approach with two states, HOLD and CASH, enabling efficient computation in linear time with constant space.