DSA Days: Stock Buy and Sell – Multiple Transactions Allowed

Link to this question

When it comes to stock trading, the goal is to maximize profit by buying and selling at the right times. In this problem, you are allowed to make multiple transactions, but with the restriction that you cannot hold more than one stock at a time. This blog explores the logic and implementation of a solution to maximize profit given a list of daily stock prices.

Problem Description

You are given an array prices[] where the element at the i-th index represents the cost of the stock on day ii. Your task is to find the maximum profit you can achieve under the following conditions:

1. You can buy and sell the stock multiple times.

2. You must sell the stock before buying it again.

3. You can only hold one stock at a time.

Approach

To maximize profit:

1. Identify consecutive increasing segments in the price array.

2. Buy at the beginning of each segment and sell at the peak.

3. Sum up the profits from all such transactions.

The key idea is to capture every increase in the price, as holding onto a stock through a declining segment does not add to the profit.

Algorithm

1. Initialize variables:

   • low to track the price at which a stock is bought.

   • high to track the price at which a stock is sold.

   • diff to store the accumulated profit.

2. Traverse the price array:

   • Compare each day's price with the next day's price.

   • If the price increases, update high to the next day's price.

   • If the price decreases, calculate the profit for the current segment (high - low), add it to diff, and reset low and high to the next day's price.

3. Handle the last segment:

   • After traversing the array, add the profit for the last increasing segment to diff.

4. Return the total profit (diff).

Code Implementation

Here is the Java implementation of the solution:

class Solution {
    public int maximumProfit(int prices[]) {
        // Initialize variables
        int low = prices[0]; // Buying price
        int high = prices[0]; // Selling price
        int diff = 0; // Accumulated profit

        // Traverse the price array
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] < prices[i + 1]) {
                // Price is increasing, update high
                high = prices[i + 1];
            } else {
                // Price is decreasing, calculate profit
                diff += high - low;
                // Reset low and high for the next segment
                low = prices[i + 1];
                high = prices[i + 1];
            }
        }

        // Add the profit for the last segment
        diff += high - low;
        return diff;
    }
}

Example Walkthrough

Input: prices[] = [100, 180, 260, 310, 40, 535, 695]

1. Initialization:

   • low = 100, high = 100, diff = 0.

2. Traverse Array:

   • Day 0 to Day 3: Prices are increasing (100 → 310), so high = 310.

   • Day 3 to Day 4: Prices drop, calculate profit (310 - 100 = 210), update diff = 210. Reset low = 40, high = 40.

   • Day 4 to Day 6: Prices are increasing (40 → 695), so high = 695.

3. Final Segment:

   • Add profit for the last segment (695 - 40 = 655), update diff = 865.

4. Output:

   • Maximum Profit = 865.

Complexity Analysis

1. Time Complexity: O(n)O(n)

   • We traverse the price array once, performing constant-time operations.

2. Space Complexity: O(1)O(1)

   • No additional space is used; only a few variables are needed.

Example Test Cases

Test Case 1

Input: prices[] = [4, 2, 2, 2, 4]
Output: 2
Explanation: Buy on day 3 and sell on day 4 for a profit of 4−2=24 - 2 = 2.

Test Case 2

Input: prices[] = [100, 180, 260, 310, 40, 535, 695]
Output: 865
Explanation: Profit segments are 210210 and 655655.

Conclusion

This solution efficiently calculates the maximum profit by focusing on consecutive price increases and summing up the profits from all such opportunities. It ensures that no profitable opportunity is missed while maintaining simplicity and optimal performance.