import java.util.*;
 
/*
 *   Best days to buy and sell stock, if array of stock prices given
 *
 *Q: Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to 
 *   buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell
 *
 *   Algorithm: Go through the array in order, keeping track of the lowest stock price and the best deal you've seen so far. 
 *   Whenever the current stock price minus the current lowest stock price is better than the current best deal, 
 *   update the best deal to this new value.
 *
 */
class Ideone{
 
	public static void main(String[] args){
		int[] a = { 5, 3, 8, 12, 6, 7, 9, 3, 21, 6 };
 
		int bestBuy = a[0];
		int bestSell = a[0];
 
		int tempBuy = a[0];
		int tempSell = a[0];
 
		//Traverse across array and look for an element which will give max profit. 
		for(int i=1; i<a.length; i++){
			if(a[i]> tempSell){ //If you find element value is more than tempSell, there is possibility to sell
				tempSell = a[i];
				if(tempSell-tempBuy > bestSell-bestBuy){
					bestBuy = tempBuy;
					bestSell = tempSell;
				}
			}else if(a[i]<tempBuy){
				tempBuy = a[i];
			}
		}
		System.out.println("Best day to buy => "+ bestBuy + " best time to sell =>"+ bestSell);
	}
}