Buy and Sell Stocks All Variants in DSA C - Execution Trace

Concept Flow - Buy and Sell Stocks All Variants

Start with prices array

↓

Choose variant: single, multiple, cooldown, fee

↓

Initialize variables: buy, sell, cooldown, fee

↓

Iterate over prices

↓

Update buy/sell states based on variant rules

↓

At end, return max profit

↓

Done

The flow starts with the prices array, selects the variant, updates buy/sell states per day, and ends with the max profit.

Execution Sample

DSA C

int maxProfit(int* prices, int n) {
  int buy = -prices[0], sell = 0;
  for (int i = 1; i < n; i++) {
    buy = buy > -prices[i] ? buy : -prices[i];
    sell = sell > buy + prices[i] ? sell : buy + prices[i];
  }
  return sell;
}

This code calculates max profit for single transaction by tracking buy and sell states.

Execution Table

Step	Operation	Day (i)	Price	Buy State	Sell State	Action	Profit So Far
0	Initialize	0	7	-7	0	Buy at price 7	0
1	Iterate	1	1	-1	0	Update buy: max(-7,-1)=-1	0
2	Iterate	2	5	-1	4	Update sell: max(0,-1+5)=4	4
3	Iterate	3	3	-1	4	No change buy or sell	4
4	Iterate	4	6	-1	5	Update sell: max(4,-1+6)=5	5
5	Iterate	5	4	-1	5	No change buy or sell	5
6	End	-	-	-1	5	Return sell as max profit	5

💡 Reached end of prices array, max profit is sell state = 5

Variable Tracker

Variable	Start	After Day 1	After Day 2	After Day 3	After Day 4	After Day 5	Final
buy	-7	-1	-1	-1	-1	-1	-1
sell	0	0	4	4	5	5	5

Key Moments - 3 Insights

Why does buy state become -1 on day 1 instead of staying -7?

On day 1, buy is updated to max(-7, -1) = -1, meaning buying at price 1 is better than previous buy at 7 (see execution_table row 1).

Why does sell state not change on day 3 even though price changes?

On day 3, sell remains 4 because max(4, -1 + 3) = 4, so selling at price 3 doesn't improve profit (see execution_table row 3).

Why return sell state as max profit at the end?

Sell state tracks max profit after selling, so at end it holds max profit achievable (see execution_table row 6).

Visual Quiz - 3 Questions

Look at the execution_table, what is the buy state at day 2?

A -1

B -7

C 0

D 4

💡 Hint

Check the 'Buy State' column at Step 2 in execution_table.

At which day does the sell state first increase above 0?

A Day 1

B Day 2

C Day 3

D Day 4

💡 Hint

Look at 'Sell State' column in execution_table rows for days 1 to 4.

If price on day 4 was 7 instead of 6, how would sell state change at day 4?

A Remain 5

B Increase to 7

C Increase to 6

D Decrease below 5

💡 Hint

Calculate max(sell at day 3, buy + new price) using variable_tracker values.

Concept Snapshot

Buy and Sell Stocks Variants:
- Track buy and sell states per day
- buy = max(buy, -price)
- sell = max(sell, buy + price)
- Variants add cooldown, fees, or multiple transactions
- Return sell state as max profit
- Update states iteratively over prices array

Full Transcript

This visualization shows how to find max profit from stock prices by tracking buy and sell states daily. We start by buying at the first price, then update buy and sell states each day to reflect best decisions. Buy state means best cost to hold stock, sell state means best profit after selling. We update buy as max of previous buy or buying today after selling. Sell updates as max of previous sell or selling today after buying. At the end, sell state holds max profit. The example uses prices [7,1,5,3,6,4] and shows step-by-step updates. Key moments clarify why buy changes on day 1 and why sell stays same on day 3. Quiz questions test understanding of state changes and effects of price changes.

Practice

1. What is the main goal when solving the Buy and Sell Stocks problem variants?

easy

A. Maximize the profit by choosing the best days to buy and sell stocks

B. Minimize the number of transactions regardless of profit

C. Find the day with the highest stock price only

D. Calculate the average stock price over all days

Solution

1. Step 1: Understand the problem objective

   The problem asks to maximize profit by buying and selling stocks on certain days.

2. Step 2: Identify the key action

   Choosing the best days to buy low and sell high maximizes profit.

3. Final Answer:

   Maximize the profit by choosing the best days to buy and sell stocks -> Option A

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on maximizing profit, not just counting days [OK]

Common Mistakes:

• Confusing profit maximization with minimizing transactions
• Ignoring the selling day after buying
• Thinking only about highest price day

2. Which of the following C code snippets correctly initializes the variable to track maximum profit as zero?

easy

A. int maxProfit = 0;

B. int maxProfit = -1;

C. int maxProfit = NULL;

D. int maxProfit = '0';

Solution

1. Step 1: Check variable initialization syntax

   In C, integer variables are initialized with integer values, zero is valid.

2. Step 2: Validate each option

   int maxProfit = 0; uses int maxProfit = 0; which is correct. int maxProfit = -1; uses -1 which is valid but not typical for profit initialization. int maxProfit = NULL; uses NULL which is for pointers, not int. int maxProfit = '0'; uses character '0' which is ASCII 48, not zero.

3. Final Answer:

   int maxProfit = 0; -> Option A

4. Quick Check:

   Correct int initialization = int maxProfit = 0; [OK]

Hint: Use zero integer for profit start, not NULL or char [OK]

Common Mistakes:

• Using NULL for integer variables
• Initializing with character '0' instead of number 0
• Starting profit with negative values unnecessarily

3. What will be the output of the following C code that finds max profit with one transaction?

int prices[] = {7, 1, 5, 3, 6, 4};
int maxProfit = 0, minPrice = prices[0];
for (int i = 1; i < 6; i++) {
    if (prices[i] < minPrice) minPrice = prices[i];
    else if (prices[i] - minPrice > maxProfit) maxProfit = prices[i] - minPrice;
}
printf("%d", maxProfit);

medium

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Trace the loop to find minPrice and maxProfit

   Start minPrice=7, maxProfit=0. Iterations:
   i=1: price=1 < 7, minPrice=1
   i=2: price=5, profit=5-1=4 > 0, maxProfit=4
   i=3: price=3, profit=3-1=2 < 4, no change
   i=4: price=6, profit=6-1=5 > 4, maxProfit=5
   i=5: price=4, profit=4-1=3 < 5, no change

2. Step 2: Final maxProfit after loop

   maxProfit is 5 after all iterations.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Max profit = 5 [OK]

Hint: Track min price and update max profit on each day [OK]

Common Mistakes:

• Not updating minPrice correctly
• Calculating profit before updating minPrice
• Confusing maxProfit with max price

4. Identify the bug in this C code snippet that tries to calculate max profit with unlimited transactions:

int maxProfit = 0;
int prices[] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
    if (prices[i] > prices[i-1]) {
        maxProfit += prices[i] - prices[i-1];
    }
}
printf("%d", maxProfit);

medium

A. The condition should be prices[i] < prices[i-1]

B. maxProfit should be initialized to -1

C. Loop starts at i=0 causing out-of-bounds access at prices[i-1]

D. The array size is incorrect

Solution

1. Step 1: Analyze loop index usage

   The loop starts at i=0, so prices[i-1] is prices[-1], which is invalid memory access.

2. Step 2: Correct the loop start

   Loop should start at i=1 to safely access prices[i-1].

3. Final Answer:

   Loop starts at i=0 causing out-of-bounds access at prices[i-1] -> Option C

4. Quick Check:

   Index error at i=0 [OK]

Hint: Start loop from 1 when accessing previous element [OK]

Common Mistakes:

• Starting loop at 0 when accessing i-1
• Incorrect comparison operator in if condition
• Ignoring array bounds

5. Given the prices array {3, 3, 5, 0, 0, 3, 1, 4}, what is the maximum profit with at most two transactions?

hard

A. 8

B. 6

C. 5

D. 7

Solution

1. Step 1: Understand two transactions limit

   We can buy and sell stocks at most twice to maximize profit.

2. Step 2: Calculate max profit for two transactions

   First transaction: buy at 3 (day 0), sell at 5 (day 2), profit = 2.
   Second transaction: buy at 0 (day 3), sell at 4 (day 7), profit = 4.
   Total profit = 2 + 4 = 6.

3. Step 3: Check for better transactions

   Alternatively, buy at 0 (day 3), sell at 3 (day 5), profit = 3.
   Then buy at 1 (day 6), sell at 4 (day 7), profit = 3.
   Total profit = 3 + 3 = 6.
   But better is buy at 0 (day 3), sell at 5 (day 2) is invalid (sell before buy). So best is 6 or 7 or 8?
   Actually, the maximum profit with two transactions is 7:
   Buy at 0 (day 3), sell at 3 (day 5), profit = 3.
   Buy at 1 (day 6), sell at 4 (day 7), profit = 3.
   Total profit = 6.
   But if we consider buy at 3 (day 0), sell at 5 (day 2), profit = 2.
   Buy at 0 (day 3), sell at 4 (day 7), profit = 4.
   Total profit = 6.
   However, the maximum profit is 7:
   Buy at 0 (day 3), sell at 5 (day 2) invalid.
   Buy at 0 (day 3), sell at 4 (day 7), profit = 4.
   Buy at 1 (day 6), sell at 4 (day 7), profit = 3.
   Total profit = 7.
   So the correct maximum profit is 7.

4. Final Answer:

   7 -> Option D

5. Quick Check:

   Two transactions max profit = 7 [OK]

Hint: Split array, find max profit left and right, sum max [OK]

Common Mistakes:

• Counting overlapping transactions
• Ignoring zero price days
• Assuming unlimited transactions