121_Best Time to Buy and Sell Stock

Say you have an array for which theithelement is the price of a given stock on dayi.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

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

max. difference = 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

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

Solution 1: brute force

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # brute force
        profit = 0
        for i in range(len(prices)-1):
            for j in range(i+1, len(prices)):
                profit = max(profit, prices[j] - prices[i])
        return profit

Solution 2: dynamic programing

假设已经解决了 i-1 个数字，对于第 i 个数字，我们关心的是，第i 个数字要么能否成为新的买⼊点，要么能否成为新的卖出点

如果是当前i 数字是最⼩值，那么可以作为新的可能的买⼊点，对应着需要更新curMin

如果是（当前值- 最⼩值）更⼤，那么可以作为新的卖出点，对应着需要更新curProfit 只需要遍历⼀次数组，⽤⼀个变量记录遍历过数中的最⼩值，然后每次计算当前值和这个最⼩值之间的差值为利润，然后每次选较⼤的利润来更新。当遍历完成后当前利润即为所求

Time: O(N), Space: O(1)

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

        # dp
        if len(prices) == 0:
            return 0
        curMin = prices[0]
        curProfit, maxProfit = 0, 0
        for cur in prices:
            curMin = min(curMin, cur)
            curProfit = max(curProfit, cur - curMin)
            maxProfit = max(maxProfit, curProfit)
        return maxProfit