To find how you can maximize your gain with multiple buy-sell trades given the daily values of a stock, the task becomes finding all the profitable segments. A simple solution is to buy whenever the price is going to rise and sell when the price is going to fall.

Approach:

  1. Traverse the array of stock prices.
  2. Buy on every local minimum (a point where the price starts rising).
  3. Sell on every local maximum (a point where the price starts falling).
  4. Accumulate all profits from these transactions.

Key Idea:

You don’t need to buy and sell on every day. Instead, find the peaks and valleys:

  • Buy at every valley (when the stock price is lower than the next day’s price).
  • Sell at every peak (when the stock price is higher than the next day’s price).

Example:

Input:

prices = [1, 5, 3, 8, 4, 9]

Steps:

  1. Buy at 1 (because 1 < 5).
  2. Sell at 5 (because 5 > 3), profit = 5 - 1 = 4.
  3. Buy at 3 (because 3 < 8).
  4. Sell at 8 (because 8 > 4), profit = 8 - 3 = 5.
  5. Buy at 4 (because 4 < 9).
  6. Sell at 9 (because 9 is the last price), profit = 9 - 4 = 5.

Total profit:

4 + 5 + 5 = 14

Step-by-step Explanation of Solution:

  1. Start at day 1 and check if tomorrow’s price is higher.
  2. If tomorrow’s price is higher, buy today (we’ve found a valley).
  3. Continue checking the prices and if you find a peak (a point where tomorrow’s price is lower than today’s), sell the stock.
  4. Repeat this process for every consecutive day until the last day.

Code Implementation:

1. Python:

def maxProfit(prices):
    total_profit = 0

    for i in range(1, len(prices)):
        # If today's price is less than tomorrow's, we buy today and sell tomorrow
        if prices[i] > prices[i - 1]:
            total_profit += prices[i] - prices[i - 1]

    return total_profit

# Example usage:
prices = [1, 5, 3, 8, 4, 9]
print(f"The maximum profit is: {maxProfit(prices)}")

2. JavaScript:

function maxProfit(prices) {
    let totalProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        // If tomorrow's price is higher than today's, buy today and sell tomorrow
        if (prices[i] > prices[i - 1]) {
            totalProfit += prices[i] - prices[i - 1];
        }
    }

    return totalProfit;
}

// Example usage:
const prices = [1, 5, 3, 8, 4, 9];
console.log(`The maximum profit is: ${maxProfit(prices)}`);

3. C++:

#include <iostream>
#include <vector>
using namespace std;

int maxProfit(vector<int>& prices) {
    int totalProfit = 0;

    for (int i = 1; i < prices.size(); ++i) {
        // If tomorrow's price is higher than today's, buy today and sell tomorrow
        if (prices[i] > prices[i - 1]) {
            totalProfit += prices[i] - prices[i - 1];
        }
    }

    return totalProfit;
}

int main() {
    vector<int> prices = {1, 5, 3, 8, 4, 9};
    cout << "The maximum profit is: " << maxProfit(prices) << endl;
    return 0;
}

4. Java:

public class StockProfit {
    public static int maxProfit(int[] prices) {
        int totalProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            // If tomorrow's price is higher than today's, buy today and sell tomorrow
            if (prices[i] > prices[i - 1]) {
                totalProfit += prices[i] - prices[i - 1];
            }
        }

        return totalProfit;
    }

    public static void main(String[] args) {
        int[] prices = {1,

java
5, 3, 8, 4, 9};
System.out.println(“The maximum profit is: ” + maxProfit(prices));
}
}
“`

See also  Given two sorted arrays, find the median of the combined sorted array.

Step-by-Step Explanation:

  1. Initialize total profit to 0: We will accumulate profit as we identify buying and selling opportunities.
  2. Iterate through the prices: For each day, starting from the second day, compare the current price with the previous day.
  3. Check if there’s an increase: If today’s price is higher than yesterday’s, it means buying yesterday and selling today would give a profit.
  4. Accumulate the profit: Add the difference between today’s and yesterday’s price to the total profit.
  5. Return total profit: After iterating through the entire array, the accumulated profit is the maximum possible with multiple buy-sell trades.

Example Walkthrough:

For the input [1, 5, 3, 8, 4, 9]:

  • Buy at 1, sell at 5: Profit = 5 - 1 = 4
  • Buy at 3, sell at 8: Profit = 8 - 3 = 5
  • Buy at 4, sell at 9: Profit = 9 - 4 = 5

Total profit = 4 + 5 + 5 = 14.

Time Complexity:

  • O(n): We traverse the list of prices only once, where n is the number of days.

Space Complexity:

  • O(1): We are using a constant amount of extra space.

This method ensures you capture all the potential profits from the rises in the stock price.

To address both the basic and intermediate algorithms for stock trading efficiently,

Problem 1: Basic Algorithm (Single Buy-Sell Transaction)

The task is to find the maximum profit from one buy-sell transaction.

Solution Approach:

  • You traverse the list once, keeping track of the minimum price so far, and for each day, you calculate the profit if you sold that day.

Python Code:

def maxProfitSingleTransaction(prices):
    if not prices:
        return 0

    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

# Example usage:
prices = [7, 1, 5, 3, 6, 4]
print(f"Maximum profit with one transaction: {maxProfitSingleTransaction(prices)}")

Explanation:

  • Track the lowest price so far (min_price).
  • For each day, calculate the potential profit by subtracting min_price from the current price and update max_profit accordingly.
See also  write a program that will find how you can gain the most with a single buy-sell-trade.

Time Complexity:

  • O(n): We loop through the list of prices once.

Space Complexity:

  • O(1): We only use a few variables.

Problem 2: Intermediate Algorithm (Multiple Buy-Sell Transactions)

The task here is to maximize the profit by making multiple buy-sell transactions (buy low, sell high multiple times).

Solution Approach:

  • Traverse the list and accumulate profits by adding the difference between consecutive days whenever the stock price rises.

Python Code:

def maxProfitMultipleTransactions(prices):
    total_profit = 0

    for i in range(1, len(prices)):
        # If the price is rising, add the difference to total profit
        if prices[i] > prices[i - 1]:
            total_profit += prices[i] - prices[i - 1]

    return total_profit

# Example usage:
prices = [1, 5, 3, 8, 4, 9]
print(f"Maximum profit with multiple transactions: {maxProfitMultipleTransactions(prices)}")

Explanation:

  • We add to the profit whenever the stock price is rising, capturing the profit from each rise.

Time Complexity:

  • O(n): We loop through the list of prices once.

Space Complexity:

  • O(1): We only use a single variable (total_profit).

Complete Solution

1. JavaScript

Basic (Single Buy-Sell Transaction):
function maxProfitSingleTransaction(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;

    for (let price of prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }

    return maxProfit;
}

// Example usage:
const pricesSingle = [7, 1, 5, 3, 6, 4];
console.log(`Max profit with one transaction: ${maxProfitSingleTransaction(pricesSingle)}`);
Intermediate (Multiple Buy-Sell Transactions):
function maxProfitMultipleTransactions(prices) {
    let totalProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            totalProfit += prices[i] - prices[i - 1];
        }
    }

    return totalProfit;
}

// Example usage:
const pricesMultiple = [1, 5, 3, 8, 4, 9];
console.log(`Max profit with multiple transactions: ${maxProfitMultipleTransactions(pricesMultiple)}`);

2. C++

Basic (Single Buy-Sell Transaction):
#include <iostream>
#include <vector>
using namespace std;

int maxProfitSingleTransaction(vector<int>& prices) {
    int min_price = INT_MAX, max_profit = 0;

    for (int price : prices) {
        min_price = min(min_price, price);
        max_profit = max(max_profit, price - min_price);
    }

    return max_profit;
}

int main() {
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << "Maximum profit with one transaction: " << maxProfitSingleTransaction(prices) << endl;
    return 0;
}
Intermediate (Multiple Buy-Sell Transactions):
#include <iostream>
#include <vector>
using namespace std;

int maxProfitMultipleTransactions(vector<int>& prices) {
    int total_profit = 0;

    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] > prices[i - 1]) {
            total_profit += prices[i] - prices[i - 1];
        }
    }

    return total_profit;
}

int main() {
    vector<int> prices = {1, 5, 3, 8, 4, 9};
    cout << "Maximum profit with multiple transactions: " << maxProfitMultipleTransactions(prices) << endl;
    return 0;
}

3. Java

Basic (Single Buy-Sell Transaction):
public class StockProfit {
    public static int maxProfitSingleTransaction(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Maximum profit with one transaction: " + maxProfitSingleTransaction(prices));
    }
}
Intermediate (Multiple Buy-Sell Transactions):
public class StockProfitMultiple {
    public static int maxProfitMultipleTransactions(int[] prices) {
        int totalProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                totalProfit += prices[i] - prices[i - 1];
            }
        }

        return totalProfit;
    }

    public static void main(String[] args) {
        int[] prices = {1, 5, 3, 8, 4, 9};
        System.out.println("Maximum profit with multiple transactions: " + maxProfitMultipleTransactions(prices));
    }
}

  • Basic Algorithm: Finds the maximum profit with one buy-sell transaction by keeping track of the lowest price so far.
  • Intermediate Algorithm: Maximizes profit with multiple transactions by capturing every price increase.
See also  Given an array and a window size, find the maximum element in each sliding window.

facebookShare on Facebook
TwitterPost on X
FollowFollow us
PinterestSave

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *