# Python DP solution O(k*n) time, O(k) space

• I haved added a pre-process function to get rid of unnecessary elements.
For k greater than n/2, quickly return the maximum profit one can get

``````class Solution(object):
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
if(len(prices)<=1 or k==0 ): return 0
if(len(prices)==2): return max(0,prices[1]-prices[0])
#print len(prices)
prices=self.preProcess(prices)
if(len(prices)<=1 or k==0 ): return 0
#return 0
k=min(k,len(prices)/2)
if(k==len(prices)/2): return self.getMaxP(prices)
b=k*[-prices[0]]
s=k*[0]
ktmp=1
for i in xrange(1,len(prices)):
p=prices[i]
j=ktmp
while(j<k and b[j]!=-prices[0]): j=j+1
j=min(j,k-1)
ktmp=j
while(j>=1):
s[j]=max(s[j],b[j]+p)
b[j]=max(b[j],s[j-1]-p)
j=j-1
s[0]=max(s[0],b[0]+p)
b[0]=max(b[0],-p)
#print s
return max(s)

def preProcess(self,prices):
newp=[]
p0=prices[0]
for i in xrange(1,len(prices)):
if(prices[i]<=p0):
p0=prices[i]
else: break
if(i==len(prices)): return newp

j=i
prev=prices[j]
for j in xrange(i+1,len(prices)):
p=prices[j]
if(p<p0 and prev==p0):
p0=p
prev=p
elif(p<prev):
newp.append(p0)
newp.append(prev)
p0=p
prev=p
else: prev=p
if(prev>p0):
newp.append(p0)
newp.append(prev)
return newp

def getMaxP(self,prices):
maxp=0
for i in xrange(0,len(prices)-1):
if(i%2==0): maxp=maxp-prices[i]
else:maxp=maxp+prices[i]
if((len(prices)-1)%2==1): maxp=maxp+prices[-1]
return maxp
``````

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