# 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 sell;
};
{
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
//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)
{
}
}
}
int main()
{
int arr[]= {4, 9, 7, 15, 20};  //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array