Stock Buy And Sell Problem Using Kadane's Algorithm - AskTheCode

Java program to get max profit from Stock Buy And Sell | Java Programming Solution | AskTheCode

---

Problem:

You have super power to see the future. Use your such cool power in Stock trading and earn as much profit as you can. The authorities got the news about your super power so they introduces a condition before you that you can buy / sell only 1 Stock. You agreed and decided to earn the maximum profit from that single stock you can have.

Considering the circumstances, you decided to write a java program which will help you to make the maximum profit.

You are given an array of integers having the prices of Stock on each day. Then, you have to find the maximum profit you can make from it.

---

Input:

• Only single line consisting the values of stock separated by a space.

---

Output:

• A single line displaying the maximum profit you can make.

---

Sample Inputs:

1. 100 180 260 310 40 535 695

2. 23 21 2 31 43 04 11 2 3 44 0

---

Sample Outputs:

1. 655

2. 42

---

EXPLANATION:

Example case 1: The values of the stock are: 100, 180, 260, 310, 40, 535, 695. To get the maximum profit, you have to buy the stock in as minimal price as you can, and also have to sell it in the maximum price possible.

You buy the stock on day 0, and you sell it on day 3. You get some profit, but, found that buying the stock on day 4 and selling it on day 6 will make more profit, so, you did the same. Hence, you made a profit of 655.

---

Code:

This code have the three approaches that you can possible implement to solve such type of problem:

1. Brute force

2. Optimized Brute force

3. Kadane's Algorithm

import java.util.*;
import java.io.*;

class Array_StockBuyAndSell_1{
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		bw.write("Enter the stocks: "); bw.flush();
		String input[] = br.readLine().split(" ");
		int n = input.length;
		int[] arr = new int[n];
		for (int i=0; i<n; i++)
			arr[i] = Integer.parseInt(input[i]);
		bruteForceApproach(arr, n);
		optimized_BruteForceApproach(arr, n);
		optimized_MaxProfitSol(arr, n);
	}
	// This approach solves in O(n)
	// Space Complexity = O(1)
	public static void optimized_MaxProfitSol(int[] arr, int n) throws IOException{
		int maxProfit = 0, minSoFar = arr[0];
		for (int i=0; i<n; i++) {
			minSoFar = Math.min(minSoFar, arr[i]);
			int profit = arr[i] - minSoFar;
			maxProfit = Math.max(profit, maxProfit);
		}
		bw.write("\n"+maxProfit);
		bw.flush();
	}
	// This approach solves in O(n^2)
	// Space Complexity = O(1)
	public static void bruteForceApproach(int[] arr, int n) throws IOException{
		int maxProfit=-Integer.MIN_VALUE;
		for (int i=0; i<n; i++) {
			int currStock = arr[i];
			int currProfit = Integer.MIN_VALUE;
			for (int j=i; j<n; j++) {
					currProfit = arr[j] - currStock;
				if (currProfit > maxProfit)
					maxProfit = currProfit;
			}
		}

		bw.write("\n"+maxProfit);
		bw.flush();
	}
	// This is an optimized Brute force approach solves in O(n)
	// Space Complexity = O(n)
	public static void optimized_BruteForceApproach(int[] arr, int n) throws IOException{
		int[] aux = new int[n];
		int maxProfit = 0;
		for (int i=n-1; i>=0; i--) {
			if (i == n-1)
				aux[i] = Math.max(aux[i], arr[i]);
			else{
				aux[i] = Math.max(aux[i+1], arr[i]);
			}
		}

		for (int i=0; i<n; i++) {
			int currProfit = aux[0] - arr[i];
			maxProfit = Math.max(currProfit, maxProfit);
		}
		bw.write("\n"+maxProfit);
		bw.flush();
	}
}