Stock Buy Sell to Maximize Profit

Given an array which contains stock price on each day, find the maximum profit that you can make by buying and selling in those days. Here, we can buy and sell multiple times but only after selling a stock you can buy another stock.

Example

INPUT :
arr[] = {4, 9, 7, 15, 20}

OUTPUT :
Buy on day 0 and sell on day 1
Buy on day 2 and sell on day 4.

Time Complexity: O(n)

Algorithm

Initialize count = 0, ie number of buy sell pairs
Till the end of the array

1. find the local minima and store it as the starting index ie, buying on that day

2. find local maxima and store it as ending index ie, selling on that day

3. Increment the count

C++ Program

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

//defining a struct with buy and sell
struct Interval 
{
	int buy;
	int sell;
};
void stockBuySell(int arr[], int n)
{
	int count =0;
	//if there are no more than 1 element ie, 1 day
	if (n==1)
	{
		return;
	}
	//Initializing the array res[]
	Interval res[n/2 +1];
	int i = 0;
	//Till the end of the array
	while(i<n-1) 
	{
		//Finding the local minima
		while((i<n-1) && (arr[i+1]<=arr[i])) {
		    i++;
		}
		if (i==n-1)
		{
			break;
		}
		//Storing the local minima
		res[count].buy = i++;
		//finding the local maxima
		while((i < n) && (arr[i] >= arr[i-1])) {
		    i++;
		}
		//Storing the local maxima
		res[count].sell = i-1;
		count++;
		              
	}
	if (count==0)
	{
		cout<<"There is no day when buying the stock will make profit"<<endl;
	}
	else
	{
		for (int i = 0; i < count; ++i)
		{
			cout<<"Buy on day "<<res[i].buy<<"sell on day "<<res[i].sell<<endl; 
		}
	}
}
int main()
{
	int arr[]= {4, 9, 7, 15, 20};  //creating an array
    int n = sizeof(arr)/sizeof(arr[0]); //size of the array
    stockBuySell(arr,n);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top