Maximum difference between two elements such that larger element appears after the smaller number. OR
Stock Buy Sell to Maximize Profit.
We are given an array of N integers representing Stock Prices on a single day.
Find maximum profit that can be earned by performing 1 transaction.
We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay,
such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.
Lets understand what is the input and the expected output.
Sample 1:
Input: [100, 80, 120, 130, 70, 60, 100, 125]
Output: If we buy a stock at 60 and sell at 125 then profit is maximum (65).
Sample 2:
Input: [7, 9, 5, 6, 3, 2]
Output: If we buy a stock at 7 and sell at 9 then profit is maximum (2).
Sample 3:
Input: [6, 5, 4, 3, 2, 1] Output: Prices are in decreasing order so there will be no profit as stock prices goes on decreasing. So answer is 0.
Algorithm
For each stock price in array, we need to findout whether current number(stock price) is of lower value then previous stock we bought till now, (take one variable as lowestStockPriceTillNow and initialize initially with arr[0])
If it is lower then definitely we need to buy at lower price, so we will update lowestStockPriceTillNow variable to new lowest price we found.
Once we update lowestStockPriceTillNow, it means now we need to find ahead a number with maximum value than lowestStockPriceTillNow, so that selling on that value will give us maximum profit,
If we found the number greater than lowestStockPriceTillNow, then difference between them is the maximum profit we get till now.
Also, make sure in searching of value greater than lowestStockPriceTillNow, if we encounter number which is lower than lowestStockPriceTillNow (existing lowest), then we need to stop there as we found new lowest value which is lower than lowestStockPriceTillNow and we need to update lowestStockPriceTillNow, it means we need to buy stock at that price and repeat our higher number search again.
Look at below example and it will be more clear.
Stock Buy Sell Maximize Profit Java Program.
package javabypatel;
public class BuyingAndSellingStocksMaximizeProfit {
public static void main(String[] args) {
int profit = maximizeProfit(new int[]{100, 80, 120, 130, 70, 60, 100, 125});
System.out.println(profit);
}
public static int maximizeProfit(int[] arrStockPrice){
if(arrStockPrice == null || arrStockPrice.length < 2){
return 0;
}
int lowestStockPriceTillNow = arrStockPrice[0];
int maxProfitTillNow = 0;
for (int i = 0; i < arrStockPrice.length; i++) {
if(arrStockPrice[i] < lowestStockPriceTillNow){
lowestStockPriceTillNow = arrStockPrice[i];
}else{
if(arrStockPrice[i] - lowestStockPriceTillNow > maxProfitTillNow){
maxProfitTillNow = arrStockPrice[i] - lowestStockPriceTillNow;
}
}
}
return maxProfitTillNow;
}
}
You may also like to see
0/1 Knapsack Problem solved using Iterative and Dynamic Programming
Stock Buy Sell to Maximize Profit.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number.
How to Detect loop in linked list.
Tower Of Hanoi Program in Java.
Print Matrix Diagonally OR Diagonal order of Matrix.
Transpose of Matrix Inplace
Implement Queue using One Stack in Java (Recursive Implementation)
SOAP Vs REST Web Service, when to use SOAP, When to use REST.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Post a Comment