上一篇:算法隨筆_61:二進制求和-CSDN博客

=====

題目描述如下:

給定一個數組?prices?，它的第?i?個元素?prices[i]?表示一支給定股票第?i?天的價格。

你只能選擇?某一天?買入這只股票，并選擇在?未來的某一個不同的日子?賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回?0?。

示例 1：

輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

示例 2：

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0。

====

算法思路:

我們從左往右觀察原數組，當元素遞減時，如，prices[i] > prices[i+1]，prices[i]無需做為買入價格的候選，因為假如后面有個高于prices[i]的價格出現，那么prices[i+1]肯定是一個更好的買入價格的候選。因此，我們只需選擇遞減趨勢的最小元素即可，我們設minP做為這個最小值。

當元素開始上升時，我們計算當前元素與minP的差值diff，并取最大的價格差值res。

當元素再次遞減時，最大的差值不可能再大于剛才找到的res。但是我們可以嘗試找一個更小的minP。如果當前元素小于minP，我們更新minP。這樣，如果后面有大值出現的時候，與最新的minP的差值，才有可能大于剛才的res。

通過上述算法，我們不斷的更新res，最后得出結果。

下面是Python的代碼實現:

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""minP=prices[0]res=0for p in prices:diff=p-minPif diff < 0:minP=pelse:res=max(res, diff)return res