Best time to buy and sell

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:

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.

Example 2:

Input: [7,6,4,3,1]

Output: 0

Explanation: In this case, no transaction is done, i.e. max profit = 0.

Seen this question in a real interview before?

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """ 
        if not prices:
            return 0

        # 只能背过有一种 dp 的解决方案是 local max 和 global max 结合
        # 这种 local global 结合的题最好的理解思路是画一个 differences 的变化图
        localMax = [0] * len(prices) 
        globalMax = 0
        for i in range(1, len(prices)):
            # localMax[i] =  localMax[i - 1] + max(0, prices[i] - prices[i - 1]) # 这样的话相当于只要 price 不涨，就卖掉；但其实只要 localMax[i - 1] + prices[i] - prices[i - 1] > 0，这个 localMax 所属的 minPrice 在后面的 prices 中就还有可能有更高的值。
            localMax[i] = max(0, localMax[i - 1] + prices[i] - prices[i - 1])
            globalMax = max(globalMax, localMax[i])
        return globalMax

Memory optimization:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0

        localMax = [0] * 2
        globalMax = 0
        for i in range(1, len(prices)):
            localMax[i % 2] = max(0, localMax[(i + 2 - 1) % 2] + prices[i] - prices[i - 1])
            globalMax = max(globalMax, localMax[i % 2])
        return globalMax