Share my Python code, using arrays to store max profit from 0 to i and i+1 to n-1.


  • 1
    W
    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            
            n=len(prices)
            if n<=1:
                return 0
            prof1=[0 for i in range(n)]
            prof2=[0 for i in range(n)]
            low_p1=prices[0]
            max_p1=0
            for i in range(1,n):
                low_p1=min(low_p1,prices[i])
                max_p1=max(max_p1,prices[i]-low_p1)
                prof1[i]=max_p1
            high_p2=prices[n-1]
            max_p2=0
            for j in range(n-2,-1,-1):
                high_p2=max(high_p2,prices[j])
                max_p2=max(max_p2,high_p2-prices[j])
                prof2[j]=max_p2
            max_profit=prof1[n-1]
            for k in range(1,n-2):
                max_profit=max(max_profit,prof1[k]+prof2[k+1])
            return max_profit
    

    Use similar code of problem 121. but use two arrays.


Log in to reply
 

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