[LeetCode][Java] Best Time to Buy and Sell Stock

题目：

Say you have an array for which theithelement is the price of a given stock on dayi.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

题意：

与《Best Time to Buy and Sell Stock II》类似，，只是这次只允许进行一次买卖的行为。

算法分析：方法一：

只用记录之前最小的价格和最高的利润就够了啊

代码如下：

public int maxProfit(int[] prices){int min,profit;min=prices[0];profit=0;if (prices.length<=1)return 0;for(int i=0;i<prices.length;i++){if(prices[i]-min>profit)profit=prices[i]-min;if(prices[i]<min)min=prices[i];}return profit;}

方法二：

* 用类似动态规划的思想，到第i天买入，那么我能赚到的最大利润是多少呢？ * 就是i + 1 ~ n天中最大的股价减去第i天的。找最大股价的问题可以在找第i+1~n天的最大利润时顺便记录， * 这样就得出了一个线性方法。 *

代码如下： public int maxProfit(int[] prices){if (prices.length== 0)return 0;int maxPrice = prices[prices.length-1];int ans = 0;for(int i = prices.length – 1; i >= 0; i–){maxPrice = Math.max(maxPrice, prices[i]);ans = Math.max(ans, maxPrice – prices[i]);}return ans;}

再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。