Python solution with detailed explanation


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/78004/python-solution-with-detailed-explanation

    Best Time to Buy and Sell Stock II https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

    Insights

    • Visualize the problem on a piece of paper. Sketch a plot of prices and time instants.
    • The solution to the problem is to find all ascending sequences in an array.
    • Another solution is to find valley, peak, valley sequence. Editorial has good explanation.
    • Another super cool solution is simply to keep adding the difference in price for day i and day i-1 as long as price[i] >= price[i-1]. https://leetcode.com/articles/best-time-buy-and-sell-stock-ii/
    • Finally, there is a DP solution. On day i, you can either hold the stock or make a transaction. A solution can built up using these insights. This is a powerful idea and can also be applied to a later problem with transaction fee.

    DP solution building on two choices

    • dp[i] gives the maximum profit possible after day i.
    • On day i, we have two choices. Either we can hold the stock or we can make a transaction on day i.
    • If we decide to hold, then the maximum profit on day i is same as dp[i-1].
    • If we do a transaction, then we are selling at prices[i]. Now for the stock we are selling, say we bought at day j (ranging from 0 to i-1). Then the profit at day i is: max(prices[i]-prices[j]+dp[j-1])
    • dp[i] = max(hold, transact) = max(dp[i-1], prices[i] + max(dp[j-1]-prices[j])) j in [0, i-1]
    • Note, we can maintain a running maximum for (dp[j-1]-prices[j]). This makes the algorithm O(N).
    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            profit, max_diff = 0, float('-inf')
            for i in range(len(prices)):
                hold = profit
                transact = prices[i] + max_diff if i > 0 else 0
                max_diff = max(max_diff, profit-prices[i])
                profit = max(hold, transact)
            return profit
    

    Peak-Valley-Peak

    • Find all peaks and add to profit. Find all valleys and subtract from profit. Exclude first and last item from this. Pay special attention to the equality condition used to detect peak and valley.
    • Adjust for first element and last element.
    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            if prices == []:
                return 0
            profit = 0
            for i in range(1,len(prices)-1):
                if prices[i] <= prices[i-1] and prices[i] < prices[i+1]: # Notice the equality used prices[i] <= prices[i-1]
                    profit = profit - prices[i]
                elif prices[i] > prices[i-1] and prices[i] >= prices[i+1]: # Notice the equality used prices[i] >= prices[i+1]
                    profit = profit + prices[i]
            if len(prices)>1 and prices[0] < prices[1]:
                profit = profit - prices[0]
            if len(prices)>1 and prices[-1] > prices[-2]:
                profit = profit + prices[-1]
            return profit
    

    Ascending Solution

    • For the ascending solution, you need a start, end, and prev variable. All three variables are needed to compute the ascending sequence.
    • Set start to 0 and set end on every iteration when the current value is more than the previous value. When the current value is less than previous value, it signals the end of an ascending sequence. At that moment, update the profit and reset start and end.
    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            if prices == []:
                return 0
            profit, start, end, prev = 0, 0, None, prices[0]
            for i in range(1,len(prices)):
                if prices[i] >= prev:
                    end = i
                else:
                    if end:
                        profit = profit + prices[end]-prices[start]
                    start,end = i,None
                prev = prices[i]
            if end:
                profit = profit + prices[end]-prices[start]
            return profit
    

    Add successive differences

    • Keep adding the difference in price for day i and day i-1 as long as price[i] >= price[i-1].
    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            if prices == []:
                return 0
            profit = 0
            for i in range(1,len(prices)):
                if prices[i] >= prices[i-1]:
                    profit = profit + prices[i]-prices[i-1]
            return profit
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.