{"post":"

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:

You must buy before you can Sell. Short sales are not allowed in this problem.
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.
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>\n\n// Function to return the greater value from a and b\nint high(int a, int b) {\n    int greater;\n    if (a > b) {\n        greater = a;\n    }\n    else {\n        greater = b;\n    }\n    return greater;\n}\n\n// Function to return the highest profit\n// that we can make after buying and selling the given stocks\nint highprofit(int stock_price[], int first, int last) {\n    // If there is one or less than one element stocks can't be bought\n    if (last <= first) {\n        return 0;\n    }\n    int pres_profit;\n    // finalprofit variable initialised\n    int final_profit = 0;\n    // The day of buying stocks\n    for (int i = first; i < last; i++) {\n        // The day of selling stocks\n        for (int j = i + 1; j <= last; j++) {\n            // If there is profit at buying the stock on ith day and selling it on jth day\n            if (stock_price[j] > stock_price[i]) {\n                // Evaluating the present profit\n                pres_profit = stock_price[j] - stock_price[i]\n                              + highprofit(stock_price, first, i - 1)\n                              + highprofit(stock_price, j + 1, last);\n                // Updating the final profit\n                final_profit = high(final_profit, pres_profit);\n            }\n        }\n    }\n    return final_profit;\n}\n\nint main() {\n    int stock_price[] = { 80, 120, 65, 200, 430, 520, 600 };\n    int size = sizeof(stock_price) / sizeof(stock_price[0]);\n    std::cout << highprofit(stock_price, 0, size - 1);\n    return 0;\n}\n\n

Output

1460\n\n

# 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.\nFollowing is code for this problem.

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

Code:

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

Output

Buy on day 2 and sell on day 4\nBuy on day 4 and sell on day 5\nTotal profit earned is 10\n\n

Time Complexity:

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

\n","title":"Buy and Sell Stocks Problem","authorDetails":{"name":"Prabhnoor Maingi","slug":"prabhnoor-maingi"},"description":"Learn how to use C++ to write a program that determines the maximum profit that can be obtained from buying and selling stocks. Get step-by-step instructions and examples of how to approach this classic problem.","slug":"buy-and-sell-stocks-problem/","articleId":"636a83447bb1ce5072622b63","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}