public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
    	
    	/* 
    	 * Brutal solution
    	int maxProfit = 0;
    	
    	for(int i=0; i<prices.length - 1; i++){
    		for(int j = i + 1; j<prices.length; j++){
    			if(prices[j] - prices[i] > maxProfit){
    				maxProfit = prices[j] - prices[i];
    			}
    		}
    	}
        
    	return maxProfit;
    	*/
    	
    	//////////////////////////////////////////////////////
    	/*
    	 * Optimized solution
    	 */
    	if(prices == null || prices.length == 0)
    		return 0;
    	
    	int min = 0;
    	int maxProfit = 0;
    	for(int i=1; i<prices.length; i++){
    		if(prices[i] - prices[min] > maxProfit){
    			maxProfit = prices[i] - prices[min];
    		}
    		
    		if(prices[min] > prices[i]){
    			min = i;
    		}
    	}
    	
    	return maxProfit;
    }