If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
Given an array of integers representing stock price on single day, find max profit that can be earned by 1 transaction.
So you need to find pair (buyDay,sellDay) where buyDay < = sellDay and it should maximise the profit.
For example:
|
1 2 3 4 5 |
int arr[]={14, 12, 70, 15, 99, 65, 21, 90}; Max profit can be gain by buying at 1th day(0 based indexing) and sell at 4th day. Max profit = 99-12 =87 |
Algorithm:
Lets say we have array arr[] of stock prices.
We will track two variables :lowestPriceTillThatDay and maxProfit.
- lowestPriceTillThatDay will be initialise to arr[0].
- Iterate over stock price array arr[]
- If current element is greater than lowestPriceTillThatDay
- calculate profit.
- If profit is greater than maxProfit then update the maxProfit.
- If current element is lesser than lowestPriceTillThatDay
- update lowestPriceTillThatDay with current element.
- We will get maxProfit in the end.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public static int calculateMaxProfit(int[] arr) { int lowestPriceTillThatDay=arr[0]; int maxProfit=Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { int profit=0; if(arr[i] >lowestPriceTillThatDay) { profit=arr[i]-lowestPriceTillThatDay; // Check for maxProfit if(profit > maxProfit) { maxProfit=profit; } } else { // update lowest Price till day lowestPriceTillThatDay=arr[i]; } } return maxProfit; } |
Java Program for Stock Buy Sell to Maximize Profit:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
package org.arpit.java2blog; public class StockBuySellMain { public static void main(String[] args) { int arr[]={14, 12, 70, 15, 99, 65, 21, 90}; System.out.println("Maximum profit :"+calculateMaxProfit(arr)); } public static int calculateMaxProfit(int[] arr) { int lowestPriceTillThatDay=arr[0]; int maxProfit=Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { int profit=0; if(arr[i] >lowestPriceTillThatDay) { profit=arr[i]-lowestPriceTillThatDay; if(profit > maxProfit) { maxProfit=profit; } } else { lowestPriceTillThatDay=arr[i]; } } return maxProfit; } } |
When you run above program, you will get below output:
|
1 2 3 |
Maximum profit :87 |
Related posts
