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 complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
<code>Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
/<code>
Example 2:
<code>Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0./<code>
題目大概意思就是，股票的價格變化如數組中所示，找出最大利潤。
我們來歸納一下，[7,1,5,3,6,4]
以4賣出的時候，我們把4前面的數都比較一次，1的價格是最合適買入的，利潤為3；
以6賣出的時候，我們把6前面的數都比較一次，1的價格是最合適買入的，利潤為5；
......
最後我們求出最大利潤為5。
這樣比較的次數有些多，我們換一種思路，
3之後最大的數為6，利潤為3；
5之後最大的數為6，利潤為1；
1之後最大的數為6，利潤為5；
......
最後我們求出最大利潤為5，所以我們倒過來遍歷，把最大值計算出來即可。
貼出代碼
<code> public static int maxProfit(int[] prices) {
int maxVal = 0;
int maxSum = 0;
for (int i = prices.length - 1; i >= 0 ; i--) {
maxSum = Math.max(maxVal - prices[i], maxSum);
maxVal = Math.max(maxVal, prices[i]);
}
return maxSum;
}/<code>
分享到:
閱讀更多 v心之所向v 的文章
