Python DP and Non-DP solution

• DP solution, time 104ms

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if(len(prices)<=1): return 0
b1=-prices[0]
s1=0
b2=-prices[0]
s2=0
for i in xrange(1,len(prices)):
p=prices[i]
s2=max(s2,b2+p)
b2=max(b2,s1-p)
s1=max(b1+p,s1)
b1=max(b1,-p)

return max(s1,s2)
``````

Non-DP solution, 88ms

``````class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if(len(prices)<=1): return 0
minb=prices[0]
mini=0
for i in xrange(1,len(prices)):
p=prices[i]
if(p<=minb):
minb=p
mini=i
else:
break
#print minb,mini
trans2m=0
fixi=mini
listr=[]
i=fixi+1
while(i>fixi and i<len(prices)):
p=prices[i]
if(p>minb):
i=i+1
continue
#find partial max
dictr=self.maxPartial(prices,mini,i)
#print dictr
if(1 in dictr):
if(dictr[1]>trans2m):
trans2m=dictr[1]
listr.append(dictr[0][0])
if(len(dictr[0])>1): listr.append(dictr[0][1])
minb=p
mini=i
i=i+1
#consider the last min piece
dictr=self.maxPartial(prices,mini,i)
#print dictr
if(1 in dictr):
if(dictr[1]>trans2m):
trans2m=dictr[1]
listr.append(dictr[0][0])
if(len(dictr[0])>1): listr.append(dictr[0][1])
max1=0
max2=0
for pr in listr:
if(pr>max1):
max2=max1
max1=pr
elif(pr>max2):
max2=pr

#print trans2m
#print listr
return max(max1+max2,trans2m)

def maxPartial(self,prices,i,j):
minp=prices[i]
maxp=prices[i]
indexm=i
d={}
for k in xrange(i,j):
if(prices[k]>maxp):
maxp=prices[k]
indexm=k
if(indexm==i):
d[0]=[0]
return d
#print "max index: ",indexm
list1=[i,i]
list2=[i,i]
d[0]=[maxp-minp]
if(indexm+1<j-1):
list2=self.getMaxInc(prices,indexm+1,j)
if(list2[0]!=list2[1]):
d[0].append(prices[list2[1]]-prices[list2[0]])

if(i+1<indexm-1):
list1=self.getMaxDrop(prices,i+1,indexm)
if(list1[0]!=list1[1]):
trans2=prices[list1[0]]-minp+maxp-prices[list1[1]]
if((maxp-minp+prices[list2[1]]-prices[list2[0]]) < trans2):
d[1]=trans2
return d

def getMaxInc(self,prices,i,j):
maxt=0
mina=prices[i]
minai=i
index1=i
index2=i
for k in xrange(i,j):
if(prices[k]<mina):
mina=prices[k]
minai=k
elif(prices[k]-mina>maxt):
maxt=prices[k]-mina
index1=minai
index2=k
return [index1,index2]

def getMaxDrop(self,prices,i,j):
maxt=0
maxa=prices[i]
maxai=i
index1=i
index2=i
for k in xrange(i,j):
if(prices[k]>maxa):
maxa=prices[k]
maxai=k
elif(maxa-prices[k]>maxt):
maxt=maxa-prices[k]
index1=maxai
index2=k
return [index1,index2]
``````

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