Monday, 17 July 2017

Algorithms | Stock Buy Sell to Maximize Profit

The cost of a stock on each day is given in an array; find the max profit that you can make by buying and selling in those days.

Example:
If the given array is {200, 280, 360, 410, 140, 635, 795}, the maximum profit can be earned by buying on day 0, selling on day 3. Again buy on day 4 and sell on day 6. If the given array of prices is sorted in decreasing order, then profit cannot be earned at all.

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 the end is not reached.

package com.geeks.dp;

private static void stockBuySell(int price[], int size) {

int idxMinima = 0, idxMaxima = 0, count = 0, i = 1, profit = 0;

/** For Zeroth index, we will compare only right side element.*/
boolean minima = price[0]<price[1]?true:false;

while(i<size-1) {

boolean pairFound = false;
/**
* Find the MINIMA:
*         MINIMA is the point where left and right element is greater to it.
*         For Zeroth index, we will compare only right side element.
**/
while(!minima && i<size-1) {
if(price[i]<price[i-1] && price[i]<price[i+1]) {
idxMinima = i;
minima = true;
break;
}
i++;
}

/**
* We need to find the MAXIMA if there is any MINIMA exists.
* MAXIMA is point to which left and right element
**/
while(i<size) {
if(minima && price[i]>=price[i-1] && (i==size-1 || price[i]>=price[i+1])) {
idxMaxima = i;
count++;
pairFound = true;
minima = false;
profit += price[idxMaxima] - price[idxMinima];
break;
}
i++;
}

if(pairFound) {
}
}

if(count==0) {
System.out.println("No Buy sell pair found to earn profit");
} else {
System.out.println("Above given "+count+" Buy sell pair will give the profit of Rs."+profit);
}
}

public static void main(String args[]) {
/** stock prices on consecutive days .*/
//int price[] = {100, 180, 260, 310, 40, 535, 695, 695, 695, 695};
int price[] = {180, 160, 110, 40};
int n = price.length;

/* Calculate the Maximum profit buy sells.*/