Best Time To Buy And Sell Stock

Name: Merge Overlapping Intervals
Brand: LogicMojo
SKU: .
Availability: InStock
Rating: 4.8 (230 reviews)

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Best Time To Buy And Sell Stock
Naive Approach
Efficient Approach

Logicmojo - Updated Aug 28, 2021

Problem Statement: Best Time To Buy And Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example :

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

We have presented two approaches to find the two elements:

• Naive Approach
• Efficient Approach

Naive Approach

A basic strategy is to try purchasing and selling stocks every day when they are profitable, and to keep track of the total profit thus far.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int maxProfit(int price[], int start, int end)
{

	if (end <= start)
		return 0;

	int profit = 0;

	for (int i = start; i < end; i++) {

		for (int j = i + 1; j <= end; j++) {

			if (price[j] > price[i]) {

				int curr_profit = price[j] - price[i]
								+ maxProfit(price, start, i - 1)
								+ maxProfit(price, j + 1, end);

				profit = max(profit, curr_profit);
			}
		}
	}
	return profit;
}

int main()
{
	int price[] = { 100, 180, 260, 310,
					40, 535, 695 };
	int n = sizeof(price) / sizeof(price[0]);

	cout << maxProfit(price, 0, n - 1);

	return 0;
}

Java Implementation:

import java.util.*;

class Main
{

static int maxProfit(int price[], int start, int end)
{

	if (end <= start)
		return 0;
	int profit = 0;

	for (int i = start; i < end; i++)
	{

		for (int j = i + 1; j <= end; j++)
		{

			if (price[j] > price[i])
			{

				int curr_profit = price[j] - price[i]
								+ maxProfit(price, start, i - 1)
								+ maxProfit(price, j + 1, end);

				profit = Math.max(profit, curr_profit);
			}
		}
	}
	return profit;
}

public static void main(String[] args)
{
	int price[] = { 100, 180, 260, 310,
					40, 535, 695 };
	int n = price.length;

	System.out.print(maxProfit(price, 0, n - 1));
}
}

Python Implementation:

def maxProfit(price, start, end):

	if (end <= start):
		return 0;

	profit = 0;

	for i in range(start, end, 1):

		for j in range(i+1, end+1):

			if (price[j] > price[i]):
				
				curr_profit = price[j] - price[i] +\
							maxProfit(price, start, i - 1)+ \
							maxProfit(price, j + 1, end);

				profit = max(profit, curr_profit);

	return profit;

if __name__ == '__main__':
	price = [100, 180, 260, 310, 40, 535, 695];
	n = len(price);

	print(maxProfit(price, 0, n - 1));

Approach 2: Efficient Approach

f we can only buy and sell once, we can apply the following algorithm. The most significant difference between two parts. We are permitted to buy and sell many times here.

The solution to this problem is as follows.

Find the local minima and save it as the index to start with. Return if it doesn't exist.
Find and save the local maxima as an ending index. Set the finishing index to the end if we get to the end.
Refresh the solution (Increment count of buy-sell pairs)
if you haven't reached the end yet, repeat the instructions above.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

void stockBuySell(int price[], int n)
{
	if (n == 1)
		return;

	int i = 0;
	while (i < n - 1) {

		while ((i < n - 1) && (price[i + 1] <= price[i]))
			i++;

		if (i == n - 1)
			break;

		int buy = i++;

		while ((i < n) && (price[i] >= price[i - 1]))
			i++;

		int sell = i - 1;

		cout << "Buy on day: " << buy
			<< "\t Sell on day: " << sell << endl;
	}
}

int main()
{
	int price[] = { 100, 180, 260, 310, 40, 535, 695 };
	int n = sizeof(price) / sizeof(price[0]);

	stockBuySell(price, n);

	return 0;
}

Java Implementation:

import java.util.ArrayList;

class Interval {
	int buy, sell;
}

class StockBuySell {
	void stockBuySell(int price[], int n)
	{
		if (n == 1)
			return;

		int count = 0;

		ArrayList<Interval> sol = new ArrayList<Interval>();

		int i = 0;
		while (i < n - 1) {
			while ((i < n - 1) && (price[i + 1] <= price[i]))
				i++;

			if (i == n - 1)
				break;

			Interval e = new Interval();
			e.buy = i++;

			while ((i < n) && (price[i] >= price[i - 1]))
				i++;

			e.sell = i - 1;
			sol.add(e);

			count++;
		}

		if (count == 0)
			System.out.println("There is no day when buying the stock "
							+ "will make profit");
		else
			for (int j = 0; j < count; j++)
				System.out.println("Buy on day: " + sol.get(j).buy
								+ "	 "
								+ "Sell on day : " + sol.get(j).sell);

		return;
	}

	public static void main(String args[])
	{
		StockBuySell stock = new StockBuySell();

		int price[] = { 100, 180, 260, 310, 40, 535, 695 };
		int n = price.length;

		stock.stockBuySell(price, n);
	}
}

Python Implementation:

def stockBuySell(price, n):
	
	if (n == 1):
		return
	
	i = 0
	while (i < (n - 1)):
		
		while ((i < (n - 1)) and
				(price[i + 1] <= price[i])):
			i += 1
		
		if (i == n - 1):
			break
		
		buy = i
		i += 1
		
		while ((i < n) and (price[i] >= price[i - 1])):
			i += 1
			
		sell = i - 1
		
		print("Buy on day: ",buy,"\t",
				"Sell on day: ",sell)
		
price = [100, 180, 260, 310, 40, 535, 695]
n = len(price)

stockBuySell(price, n)

Time Complexity: The outer loop runs till I become n-1. The inner two loops increment value of I in every iteration. So overall time complexity is O(n)

With this article at Logicmojo, you must have the complete idea of solving Best Time To Buy And Sell Stock problem.