Recent Posts

Buy and Sell Stocks Problem

Problem:

You are given an array of stock prices in chronological order. You can Buy or Sell at any price in the array. You must follow the following rules:

  1. You must buy before you can Sell. Short sales are not allowed in this problem.
  2. We are looking for a single Buy and Sell combination that yields the highest profit. As long as the Buy is before the Sell this is a valid transaction.
  3. You are to return the maximum profit that you can achieve. This problem could be changed to return the prices, or the indexes of the values as well.

Example:

Given the following prices: [2,11,1,4,7], the maximum profit you can make is 9. This is achieved by buying at 2, and selling at 11.

# Brute Force Approach

A simple approach is to try buying the stocks and selling them on every single day when profitable and keep updating the maximum profit so far.

Below is the implementation of the above approach:

Code:

#include <iostream>

// Function to return the greater value from a and b
int high(int a, int b) {
    int greater;
    if (a > b) {
        greater = a;
    }
    else {
        greater = b;
    }
    return greater;
}

// Function to return the highest profit
// that we can make after buying and selling the given stocks
int highprofit(int stock_price[], int first, int last) {
    // If there is one or less than one element stocks can't be bought
    if (last <= first) {
        return 0;
    }
    int pres_profit;
    // finalprofit variable initialised
    int final_profit = 0;
    // The day of buying stocks
    for (int i = first; i < last; i++) {
        // The day of selling stocks
        for (int j = i + 1; j <= last; j++) {
            // If there is profit at buying the stock on ith day and selling it on jth day
            if (stock_price[j] > stock_price[i]) {
                // Evaluating the present profit
                pres_profit = stock_price[j] - stock_price[i]
                              + highprofit(stock_price, first, i - 1)
                              + highprofit(stock_price, j + 1, last);
                // Updating the final profit
                final_profit = high(final_profit, pres_profit);
            }
        }
    }
    return final_profit;
}

int main() {
    int stock_price[] = { 80, 120, 65, 200, 430, 520, 600 };
    int size = sizeof(stock_price) / sizeof(stock_price[0]);
    std::cout << highprofit(stock_price, 0, size - 1);
    return 0;
}

Output

1460

# Efficient Approach

If we are allowed to buy and sell only once, then we can use following algorithm –  Maximum difference between two elements. Here we are allowed to buy and sell multiple times.
Following is code for this problem.

  1. Find the local minima and store it as starting index. If not exists, return.
  2. Find the local maxima. and store it as ending index. If we reach the end, set the end as ending index.
  3. Update the solution (Increment count of buy sell pairs)
  4. Repeat the above steps if end is not reached.

Code:

#include <iostream>

// Function to find highest profit that we can make by buying
// and selling shares any number of times
int highprofit(int stock_price[], int size) {
    // initialise final_profit gained
    int final_profit = 0;
    // initialise local minima to first element's index
    int j = 0;
    // starting from second element
    for (int i = 1; i < size; i++) {
        // updating local minima if decreasing sequence is found
        if (stock_price[i - 1] > stock_price[i]) {
            j = i;
        }
        // if present element is greatest(greater than
        // previous and next element) then sell shares
        if (stock_price[i - 1] <= stock_price[i] &&
            (i + 1 == size || stock_price[i] > stock_price[i + 1])) {
            final_profit += (stock_price[i] - stock_price[j]);
            std::cout << "Buy on day " << j + 1 << " and sell on day " << i + 1 << "\n";
        }
    }
    return final_profit;
}

int main() {
    int stock_price[] = { 1, 6, 2, 7, 3, 4, 5 };
    int size = sizeof(stock_price) / sizeof(stock_price[0]);
    std::cout << "\nTotal profit earned is " << highprofit(stock_price, size);
    return 0;
}

Output

Buy on day 2 and sell on day 4
Buy on day 4 and sell on day 5
Total profit earned is 10

Time Complexity:

The time complexity of the above code is O(n).

Buy and Sell Stocks Problem