Python O(n) easy to understand solution


  • 0
    A
    class Solution(object):
        def maxProfit(self, p):
    
            if len(p)<=1:
                return 0
                
            maxp=p[1]
            n=len(p)
            minp=p[0]
            profit=0
            i=1
            if n==2 and p[1]>p[0]:
                return p[1]-p[0]
                
            while i<n-1:
             
                while i<n-1 and p[i]<p[i+1]:
                        
                    maxp=p[i+1]
                    minp=min(minp,p[i])
                    i+=1
                
                if maxp>minp:
                    profit+=maxp-minp
               
                
                if i<n-1:        
                    minp=p[i+1]
                    maxp=p[i+1]
                
                i+=1
            
                    
            return profit

Log in to reply
 

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