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

Ankit says

July 26, 2015 at 6:08 amCan you explain why this solution would work?

I am not getting the solution.

Dhaval Dave says

September 23, 2015 at 2:41 pmAS we can buy and sell maximum time, we should find min price to buy and max price to sell for first time, and same process to follow for rest of price

ex : [ 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.

so we are finding local min and local max.. see algorithm, hope it helps