Maximize Profit by Selling and Buying Shares

• Write a program to maximize the profit by buying and selling stocks.
• Algorithm to gain maximum profit in share trading.

Given the share price of a company for N days in an array. Find the maximum profit we can make by buying and selling stocks on any day. You can buy or sell shares multiple times not necessarily only once. You can do any number of transactions without any brokerage charge.
For Example :

Share Price Array : 20, 45, 76, 42, 15, 37, 100, 120, 90, 105
Output :
Buy at : 20    Sell at : 76
Buy at : 15    Sell at : 120

---

Let inputArray be an integer array if size N containing share prices.

Algorithm to maximize profit for stocks buying and selling

• We can maximize profit by buying shares at local minima and they selling at next local maxima.
• inputArray[i] is local minima if inputArray[i-1] > inputArray[i] < inputArray[i+1]
• inputArray[i] is local Maxima if inputArray[i-1] < inputArray[i] > inputArray[i+1]
• Traverse inputArray and find local minima(buying shares index) and then next local maxima(selling shares index).
• Continue till end of the inputArray. IF we don't find selling index till end of array set last index as selling index.

Time Complexity : O(n)

C program to maximize profit of buying ans selling stocks

#include<stdio.h>
#include<limits.h>

/*Prints the Optimal Buy and Sell transaction to 
maximize profit */
void printStockTrade(int *sharePrice, int size) {
 /* Array to store selling and buying days */
 int buy[size/2 +1], sell[size/2 +1];
    /* Number of Buy-Sell transactions */
    int i, tradeCount = 0;
    /* We need share prices of atleast two days .. such 
 that we can buy shares on first day and sell on another */
    if (size == 1)
        return;
 
    for(i = 0; i < size-1; i++) {
        /* Find local Minima. sharePrice[i] is local Minima if 
  sharePrice[i-1] > sharePrice[i] < sharePrice[i+1] */
        while((i < size-1) && (sharePrice[i+1] <= sharePrice[i]))
            i++;
        
        /* If no local minima found */
        if (i == size-1)
            break;
 
        /* Store buying date in buy array, now we 
  have to find selling point */
        buy[tradeCount] = i++;
 
        /* Find local Maxima. sharePrice[i] is local Maxima if 
  sharePrice[i-1] < sharePrice[i] > sharePrice[i+1] */
        while((i < size-1) && (sharePrice[i] >= sharePrice[i-1]))
            i++;
 
        /*Found Local Maxima. Store it in sell Array */
        sell[tradeCount] = i-1;
         
        tradeCount++;
    }
 
    if (tradeCount == 0)
        printf("No Profitable Transaction Possible\n");
    else {
       for(i = 0; i < tradeCount; i++)
          printf("Buy at : %d    Sell at : %d\n", sharePrice[buy[i]], sharePrice[sell[i]]);
    }
 
    return;
}
 
int main() {
    int array[10] = {20, 45, 76, 42, 15, 37, 100, 120, 90, 105};

    printStockTrade(array, 10);
    
    return 0;
}

Output

Buy at : 20    Sell at : 76
Buy at : 15    Sell at : 120