public int maxProfit(int[] prices) {
		if (prices.length == 0)
			return 0;
		
		int[] maxProfits = new int[prices.length]; // save the max profits
		maxProfits[0] = 0;
		
		// ordered search
		int minPrice = prices[0];
		int maxProfit = 0;
		int profit = 0;
		for (int i = 1; i < prices.length; i++) {
			profit = prices[i] - minPrice;
			if (profit > maxProfit){
				maxProfit = profit;
			}
			maxProfits[i] = maxProfit;
			if (prices[i] < minPrice){
				minPrice = prices[i];
			}
		}
		
		// reversed order search
		int both = maxProfits[prices.length-1];
		int maxPrice = prices[prices.length-1];
		maxProfit = 0;
		int temp = 0;
		for (int i = prices.length-2; i>=0; i--) {
			profit = maxPrice - prices[i];
			if (profit > maxProfit){
				maxProfit = profit;
			}
			temp = maxProfit + maxProfits[i];
			if (temp > both){
				both = temp;
			}
			if (prices[i] > maxPrice){
				maxPrice = prices[i];
			}			
		}
		
		return both;
	}