初級演算法篇之數組 <2>

來自專欄 Python異世界的刷題之路

題目：122.買賣股票的最佳時機 II

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。設計一個演算法來計算你所能獲取的最大利潤。你可以儘可能地完成更多的交易（多次買賣一支股票）。注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

測試示例:

示例 1:輸入: [7,1,5,3,6,4]輸出: 7示例 2:輸入: [1,2,3,4,5]輸出: 4示例 3:輸入: [7,6,4,3,1]輸出: 0

解題開始:

#1.分析題目要求：

1.第i個值就是代表第i天。2.需要計算出一共最大的利潤，也就是差值和最大。3.不能同時參與多筆交易，也就是購買了就不能再買，需要出售後，才可以再買。4.本題沒有限制空間複雜度以及時間複雜度。

#2.思路1:

1.假定第一個值是最大的和最小的，設為max,min===> 也就是 max = min = array[0]2.進行遍歷列表， 2.1如果後面有值大於初值， max = array[i],然後繼續遍歷。 2.2如果後面有一次小於最大值時,那麼就跳出循環。 3.計算差值，然後k = i ，並進行新的一輪求最大差值 4.返回sum 即為最大利潤。

#2.思路2:

1.從第一個元素，兩個兩個比較，比如，第一天和第二天比較，第二天和第三天比較。2.如果第二天比第一天大，那麼就相減 sum += (array[1] - array[0])3.遍歷完，最後的sum即為最大利潤

#3.思路1的代碼：

class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ k = 0 sum = 0 if len(prices)<=1: #如果數組長度小於2,都不用執行程序，直接為0 return sum while True: #大循環 max = min = prices[k] #設定初值 #尋找後續值中是否有更大的。 for i in range(k+1, len(prices)): if prices[i] < max: break max = prices[i] sum += (max-min) k = i if k+1 == len(prices): break return sumif __name__ == "__main__": test = [7,1,5,3,6,4] test2 = [1,2,3,4,5] test3 = [7,6,4,3,1] print(Solution().maxProfit(test)) print(Solution().maxProfit(test2)) print(Solution().maxProfit(test3))

#3.思路2的代碼：

class Solution: def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ sum = 0 for i in range(len(prices)-1): if prices[i+1] > prices[i]: sum += prices[i+1] - prices[i] return sumif __name__ == "__main__": test = [7,1,5,3,6,4] test2 = [1,2,3,4,5] test3 = [7,6,4,3,1] print(Solution().maxProfit(test)) print(Solution().maxProfit(test2)) print(Solution().maxProfit(test3))

推薦閱讀：