Java  

Buy Stock with Transaction Fee

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:

  • Buy and sell stocks multiple times

  • But you must sell before buying again

  • Every transaction (buy + sell) incurs a fee k

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

  • You currently own a stock

  • Profit includes cost of buying

hold = max(hold, cash - price)

2. CASH state

  • You do NOT own a stock

  • Profit after selling stock

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

State Transitions

For each price:

Sell decision:

  • Sell stock today or not

Buy decision:

  • Buy stock today or not

Step-by-Step Approach

Step 1: Initialization

  • hold = -arr[0] → buying first stock

  • cash = 0 → no stock initially

Step 2: Traverse prices

For each day:

  • Update cash (selling decision)

  • Update hold (buying decision)

Step 3: Return result

  • Final answer = cash (max profit without holding stock)

Example

Input:

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

Step-by-step transactions:

  • Buy at 1 → Sell at 7
    Profit = 7 - 1 - 2 = 4

  • Buy at 2 → Sell at 8
    Profit = 8 - 2 - 2 = 4

Final Profit:

8

Java 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:

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

Output:

8

Complexity

  • Time Complexity: O(n)

  • Space Complexity: O(1)

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:

  • HOLD (stock in hand)

  • CASH (no stock in hand)

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.

Membership not found