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

Concept Flow - Buy and Sell Stocks All Variants

Start

↓

Choose Variant

↓

Variant 1: One Transaction

↓

Track min price, max profit

↓

Update profit if price - min_price > profit

↓

End

↓

Variant 2: Multiple Transactions

↓

Sum all positive price differences

↓

End

↓

Variant 3: At Most Two Transactions

↓

Use DP arrays: left_profit, right_profit

↓

Combine max profits from left and right

↓

End

↓

Variant 4: At Most K Transactions

↓

Use DP table: dp[k

↓

Calculate max profit with k transactions

↓

End

The flow starts by selecting the variant of the stock buy-sell problem, then follows the specific steps to calculate max profit according to that variant.

Execution Sample

DSA C++

int maxProfitOneTransaction(vector<int>& prices) {
    int minPrice = INT_MAX, maxProfit = 0;
    for (int price : prices) {
        minPrice = min(minPrice, price);
        maxProfit = max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

Calculates max profit from one buy-sell transaction by tracking minimum price and maximum profit.

Execution Table

Step	Operation	minPrice	maxProfit	Current Price	Visual State
1	Initialize minPrice=∞, maxProfit=0	∞	0	-	[]
2	Price=7: minPrice=min(∞,7)=7	7	max(0,7-7)=0	7	[7]
3	Price=1: minPrice=min(7,1)=1	1	max(0,1-1)=0	1	[7,1]
4	Price=5: minPrice=1, maxProfit=max(0,5-1)=4	1	4	5	[7,1,5]
5	Price=3: minPrice=1, maxProfit=max(4,3-1)=4	1	4	3	[7,1,5,3]
6	Price=6: minPrice=1, maxProfit=max(4,6-1)=5	1	5	6	[7,1,5,3,6]
7	Price=4: minPrice=1, maxProfit=max(5,4-1)=5	1	5	4	[7,1,5,3,6,4]
8	End: maxProfit=5	1	5	-	[7,1,5,3,6,4]

💡 All prices processed, maxProfit holds the maximum profit from one transaction.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
minPrice	∞	7	1	1	1	1	1	1
maxProfit	0	0	0	4	4	5	5	5
Current Price	-	7	1	5	3	6	4	-

Key Moments - 3 Insights

Why do we update minPrice before calculating maxProfit?

Because maxProfit depends on the lowest price seen so far. Updating minPrice first ensures we compare current price with the smallest buy price (see steps 2 and 3 in execution_table).

Why does maxProfit not decrease even if price drops?

maxProfit only updates if current price minus minPrice is greater than previous maxProfit. If price drops, maxProfit stays the same (see steps 5 and 7).

What if prices array is empty?

The loop never runs, minPrice stays ∞ and maxProfit stays 0, so function returns 0 profit safely.

Visual Quiz - 3 Questions

Look at the execution_table, what is minPrice after processing price 3?

A 1

B 5

C 3

D 7

💡 Hint

Check step 5 in execution_table where price=3 is processed.

At which step does maxProfit first become 4?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look at maxProfit column in execution_table rows.

If the prices array was strictly decreasing, what would maxProfit be at the end?

A Negative value

B 0

C Price difference between first and last

D Infinity

💡 Hint

Refer to variable_tracker and note maxProfit never decreases below 0.

Concept Snapshot

Buy and Sell Stocks Variants:
- Variant 1: One transaction max profit = max(price - minPrice)
- Variant 2: Multiple transactions sum all positive diffs
- Variant 3: Two transactions use DP left/right profits
- Variant 4: K transactions use DP table dp[k][i]
Key: Track min price and update max profit accordingly.

Full Transcript

This concept covers different ways to find maximum profit from stock prices by buying and selling. The simplest variant tracks the lowest price seen and calculates profit by subtracting it from current price, updating max profit if better. More complex variants use dynamic programming to handle multiple transactions. The execution table shows step-by-step how minPrice and maxProfit change as prices are processed. Key moments clarify why minPrice updates first and why maxProfit never decreases. The visual quiz tests understanding of these steps. The snapshot summarizes the variants and main approach.

Practice

1. What is the main goal when solving the Buy and Sell Stocks problem with only one transaction allowed?

easy

A. Sell before buying to maximize profit

B. Minimize the buying price regardless of selling price

C. Buy and sell on the same day to avoid loss

D. Maximize the difference between a later selling price and an earlier buying price

Solution

1. Step 1: Understand the problem constraints

   The problem allows only one buy and one sell, so the goal is to find the maximum profit from one pair of days where buying day is before selling day.

2. Step 2: Identify the profit calculation

   Profit = selling price - buying price. We want to maximize this difference with the buying day before selling day.

3. Final Answer:

   Maximize the difference between a later selling price and an earlier buying price -> Option D

4. Quick Check:

   Profit = sell price - buy price [OK]

Hint: Find max difference with buy day before sell day [OK]

Common Mistakes:

• Ignoring the order of buy and sell days
• Trying to minimize price without considering selling
• Assuming multiple transactions allowed

2. Which of the following C++ code snippets correctly initializes a vector of stock prices for the Buy and Sell Stocks problem?

easy

A. std::vector prices = (7, 1, 5, 3, 6, 4);

B. std::vector<int> prices = {7, 1, 5, 3, 6, 4};

C. vector prices = [7, 1, 5, 3, 6, 4];

D. std::vector<int> prices = (7, 1, 5, 3, 6, 4);

Solution

1. Step 1: Recall correct vector initialization syntax

   In C++, a vector of integers is initialized with curly braces and type specified: std::vector<int> prices = {values};

2. Step 2: Check each option

   std::vector<int> prices = {7, 1, 5, 3, 6, 4}; uses correct syntax with std::vector<int> and curly braces. Options A, B, and D use incorrect syntax for vector initialization.

3. Final Answer:

   std::vector<int> prices = {7, 1, 5, 3, 6, 4}; -> Option B

4. Quick Check:

   Use std::vector<int> and braces {} [OK]

Hint: Use std::vector<int> and curly braces {} to initialize [OK]

Common Mistakes:

• Using square brackets [] instead of curly braces {}
• Omitting the type <int>
• Using parentheses () instead of braces

3. What is the output of the following C++ code that finds the maximum profit with unlimited transactions allowed?

std::vector<int> prices = {7, 1, 5, 3, 6, 4};
int maxProfit = 0;
for (int i = 1; i < prices.size(); i++) {
    if (prices[i] > prices[i - 1]) {
        maxProfit += prices[i] - prices[i - 1];
    }
}
std::cout << maxProfit << std::endl;

medium

A. 7

B. 5

C. 8

D. 6

Solution

1. Step 1: Understand the loop and profit calculation

   The code adds profit for every day where price increases from previous day, summing all positive differences.

2. Step 2: Calculate profits day by day

   Day 1 to 2: 1 - 7 = -6 (no profit)
   Day 2 to 3: 5 - 1 = 4 (add 4)
   Day 3 to 4: 3 - 5 = -2 (no profit)
   Day 4 to 5: 6 - 3 = 3 (add 3)
   Day 5 to 6: 4 - 6 = -2 (no profit)
   Total profit = 4 + 3 = 7

3. Final Answer:

   7 -> Option A

4. Quick Check:

   Sum of positive differences = 7 [OK]

Hint: Sum all positive price differences for unlimited transactions [OK]

Common Mistakes:

• Adding negative differences as profit
• Only considering one transaction
• Miscounting indices in loop

4. Identify the bug in this C++ code snippet that tries to find the maximum profit with only one transaction allowed:

std::vector<int> prices = {7, 1, 5, 3, 6, 4};
int minPrice = INT_MAX;
int maxProfit = 0;
for (int i = 0; i < prices.size(); i++) {
    if (prices[i] < minPrice) {
        minPrice = prices[i];
    } else if (prices[i] - minPrice > maxProfit) {
        maxProfit = prices[i] - minPrice;
    }
}
std::cout << maxProfit << std::endl;

medium

A. No bug, code works correctly

B. minPrice should be initialized to 0

C. maxProfit should be initialized to INT_MIN

D. Loop should start from i = 1 instead of 0

Solution

1. Step 1: Analyze initialization and loop

   minPrice is set to INT_MAX to find minimum price correctly. maxProfit starts at 0. Loop from 0 to end checks each price.

2. Step 2: Check logic correctness

   For each price, update minPrice if current price is lower. Else, calculate profit and update maxProfit if higher. This correctly finds max profit with one transaction.

3. Final Answer:

   No bug, code works correctly -> Option A

4. Quick Check:

   Correct minPrice and maxProfit updates [OK]

Hint: Initialize minPrice to INT_MAX and loop from 0 [OK]

Common Mistakes:

• Starting loop from 1 and missing first price
• Initializing minPrice to 0 causing wrong min
• Initializing maxProfit to INT_MIN causing negative profits

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

hard

A. 5

B. 7

C. 6

D. 8

Solution

1. Step 1: Understand two transactions limit

   We can buy and sell at most twice. We must find two pairs of buy-sell days maximizing total profit without overlap.

2. Step 2: Calculate max profit with two transactions

   First transaction: Buy at 3 (day 1), sell at 5 (day 3) profit = 2
   Second transaction: Buy at 0 (day 4), sell at 4 (day 8) profit = 4
   Total profit = 2 + 4 = 6

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum of two best transactions = 6 [OK]

Hint: Split prices into two parts, sum max profits [OK]

Common Mistakes:

• Counting overlapping transactions
• Only considering one transaction
• Misidentifying buy/sell days