Stock Buy Sell to Maximize Profit

Stock Price on each day is given in an array.
Example : [ 10, 12, 7, 5, 9, 15, 13, 18 ] Find the max profit that you can make by buying and selling in those days.
max profit is when u buy on 5 sell on 15, buy on 13 and sell on 18.

If you can just buy and sell once thenn?
-> you can think for Max and Min such that index_Max > index_Min.
so this code is extension of Max and Min such that index_Max > index_Min, as we are allowed to buy and sell it more times.

Strategy : Start from 0th day, get Stock at minimum price (by comparing it with next day price). and Sell as soon as we get profit.
{ this is called finding local minima and maxima } 

Following is algorithm 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.

Now along with it, w’ll store its indexes in our solution to calculate prices.

#include <stdio.h>
struct Interval{
//This structure to store results in local mim and max
 int buy;
 int sell;
};
 
void stockBuySell(int price[], int n)
{
 if (n < 1)
 return;
 
 int countSol = 0; 
 //count of total solutions
 
 Interval solution[n/2 + 1]; //sol
 // solution vector
 int i = 0;
 while (i < n-1)
 {
 // Find Local Minima.
 while ((i < n-1) && (price[i+1] <= price[i]))
 i++;
 
 // If we reached the end, break as no further solution possible
 if (i == n-1)
 break;
 
 // Store the index of minima
 solution[countSol].buy = i++;
 
 // Find Local Maxima.
 while ((i < n) && (price[i] >= price[i-1]))
 i++;
 
 // Store the index of maxima
 solution[countSol].sell = i-1;
 
 // Increment count of buy/sell pairs
 countSol++;
 }
 
 int totalProfit=0;
 //Calculate total Profit
 
 if (countSol == 0)
 printf("Sorry NO Profit Possibe\n");
 else
 {
 for (int i = 0; i < countSol; i++){
 totalProfit += price[solution[i].sell]-price[solution[i].buy];
 printf("Buy on day: %d\t Sell on day: %d Profit %d : \n", solution[i].buy, solution[i].sell, price[solution[i].sell]-price[solution[i].buy] );
 }
 printf("Total Profit %d",totalProfit);
 }
 
 return;
}
int main()
{
 int price[] = {2, 9, 10, 50, 47, 500, 100000};
 int n = sizeof(price)/sizeof(price[0]);
 stockBuySell(price, n);
 return 0;
}

You can send us mail on admin@gohired.in for queries and more interesting questions and solutions.
Find us on FACEBook :
GoHired Page  Gohired Group