Python 95%, No DP AND take advantage of LC121


  • 0
    G
    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            s1,e1,p1 = self.pro1(prices)
            p2_1 = max(self.pro1(prices[:s1])[2],self.pro1(prices[e1+1:])[2])
            p2_2 = self.pro1([-1*x for x in prices[s1+1:e1]])[2]
            return p1+max(p2_1,p2_2)
            
        def pro1(self,prices):
            if len(prices)<2:
                return (0,0,0)
            output = 0
            min_p = 0
            min_c = 0
            max_p = 0
            for i in range(len(prices)):
                if prices[i] < prices[min_c]:
                    min_c =i
                elif prices[i] - prices[min_c]> output:
                    output = prices[i] - prices[min_c]
                    max_p =i
                    min_p = min_c
                    
            return (min_p,max_p,output)

Log in to reply
 

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