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