## 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>
// 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;
}
```

**# 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.

- 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>
// 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;
}
```

**Time Complexity:**

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

Report Error/ Suggestion