RUN


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;

}

# 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;

}

Time Complexity:

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

 

Report Error/ Suggestion

Related Posts:

[yuzo_views]



Interview Questions



CopyRight © 2020

CopyRight © 2020