best-time-to-buy-and-sell-stock.py

"""

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.

"""

# V0
# IDEA : array op + problem understanding
class Solution(object):
    def maxProfit(self, prices):
        if len(prices) == 0:
            return 0
        ### NOTE : we define 1st minPrice as prices[0]
        minPrice = prices[0]
        maxProfit = 0
        ### NOTE : we only loop prices ONCE
        for p in prices:
            # only if p < minPrice, we get minPrice
            if p < minPrice:
                minPrice = p
            ### NOTE : only if p - minPrice > maxProfit, we get maxProfit
            elif p - minPrice > maxProfit:
                maxProfit = p - minPrice
        return maxProfit

# V0''
# IDEA : BRUTE FORCE (time out error)
class Solution(object):
    def maxProfit(self, prices):
        res = 0
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                #print ("i = " + str(i) + " j = " + str(j))
                if prices[j] > prices[i]:
                    diff = prices[j] - prices[i]
                    res = max(res, diff)
        return res

# V1 
# https://blog.csdn.net/coder_orz/article/details/51520971
# TO NOTE : CAN ONLY DO ONE TRANSACTION IN THE PROBLEM  
class Solution(object):
    def maxProfit(self, prices):
        if len(prices) == 0:
            return 0
        minPrice = prices[0]
        maxProfit = 0
        for p in prices:
            if p < minPrice:
                minPrice = p
            elif p - minPrice > maxProfit:
                maxProfit = p - minPrice
        return maxProfit

# V1' 
# https://blog.csdn.net/coder_orz/article/details/51520971
# IDEA : DP 
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0
        minPrice = prices[0]
        dp = [0] * len(prices)
        for i in range(0, len(prices)):
            dp[i] = max(dp[i-1], prices[i] - minPrice)
            minPrice = min(minPrice, prices[i])
        return dp[-1]

# V1''
# https://www.jiuzhang.com/solution/best-time-to-buy-and-sell-stock/#tag-highlight-lang-python
class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        total = 0
        low, high = sys.maxint, 0
        for x in prices:
            if x - low > total:
                total = x - low
            if x < low:
                low = x
        return total

# V2 
# Time:  O(n)
# Space: O(1)
class Solution(object):
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        max_profit, min_price = 0, float("inf")
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        return max_profit