原題

假設有一個數組，它的第i個元素是一個給定的股票在第i天的價格。設計一個算法來找到最大的利潤。你可以完成盡可能多的交易(多次買賣股票)。然而,你不能同時參與多個交易(你必須在再次購買前出售股票)。

給出一個數組樣例[2,1,2,0,1], 返回 2

解題思路

• 在Best Time to Buy and Sell Stock系列中，和本題最像的是Best Time to Buy and Sell Stock IV
• Best Time to Buy and Sell Stock IV中是求某個給定k次交易的最大收益，和Maximum Subarray III完全一樣
• 本題由于是可以操作任意次數，只為獲得最大收益，而且對于一個上升子序列，比如：[5, 1, 2, 3, 4]中的1, 2, 3, 4序列來說，對于兩種操作方案：
  1 在1買入，4賣出
  2 在1買入，2賣出同時買入，3賣出同時買入，4賣出
  這兩種操作下，收益是一樣的。
• 所以可以從頭到尾掃描prices，如果price[i] – price[i-1]大于零則計入最后的收益中。即貪心法

完整代碼

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        profit = 0
        for i in range(1, len(prices)):
            diff = prices[i] - prices[i - 1]
            if diff > 0:
                profit += diff
        return profit