Ramu was a lazy farmer. He had inherited a fairly large farm and a nice house from his father. Ramu leased out the farm land to others and earned a rather handsome income. His father used to keep a buffalo at home and sell its milk but the buffalo died a few days after his father did.
Ramu too wanted to make some money from buffaloes, but in a quite a different way. He decided that his future lay in speculating on buffaloes. In the market in his village, buffaloes were bought and sold everyday. The price fluctuated over the year, but on any single day the price was always the same.
He decided that he would buy buffaloes when the price was low and sell them when the price was high and, in the process, accummulate great wealth. Unfortunately his house had space for just one buffalo and so he could own at most one buffalo at any time.
Before he entered the buffalo market, he decided to examine to examine the variation in the price of buffaloes over the last few days and determine the maximum profit he could have made. Suppose, the price of a buffalo over the last $10$ days varied as
1012811111012151310101281111101215131010\quad  12\quad  8\quad  11\quad  11\quad  10\quad  12\quad  15\quad  13\quad  10
Ramu is a lazy fellow and he reckoned that he would have been willing to visit the market at most $5$ times (each time to either buy or sell a buffalo) over the last $10$ days. Given this, the maximum profit he could have made is $9$ rupees. To achieve this, he buys a buffalo on day $1$, sells it on day $2$, buys one more on day $3$ and sells it on day $8$. If he was a little less lazy and was willing to visit the market $6$ times, then he could have made more money. He could have bought on day $1$, sold on day $2$, bought on day $3$, sold on day $4$, bought on day $6$ and sold on day $8$ to make a profit of $10$ rupees.
Your task is help Ramu calculate the maximum amount he can earn by speculating on buffaloes, given a history of daily buffalo prices over a period and a limit on how many times Ramu is willing to go to the market during this period.

-----Input:-----
- The first line of the input contains two integers $N$ and $K$, where $N$ is the number of days for which the price data is available and $K$ is the maximum number of times that Ramu is willing to visit the cattle market. 
- The next $N$ lines (line $2, 3,...,N+1$) contain a single positive integer each. The integer on line $i+1$, $1 \leq i \leq N$, indicates the price of a buffalo on day $i$.

-----Output:-----
A single nonnegative integer indicating that maximum amount of profit that Ramu can make if he were to make at most $K$ trips to the market.

-----Constraints:-----
- $1 \leq N \leq 400$.
- $1 \leq K \leq 400$.
- $0 \leq$ price of a buffalo on any day $\leq 1000$

-----Sample Input 1:-----
10 5
10
12
8
11
11
10
12
15
13
10

-----Sample Output 1:-----
9

-----Sample Input 2:-----
10 6
10
12
8
11
11
10
12
15
13
10

-----Sample Output 2:-----
10

Difficulty: interview

Starter code:

Solutions:


try:
 n,k = map(int,input().split())
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass

# cook your dish here
# cook your dish here
try:
 n,k = map(int,input().split())
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass

# cook your dish here
# cook your dish here
try:
 n,k = map(int,input().split())
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass

# cook your dish here
n, k = map(int, input().split())
k=min(k,n)
if k%2==1:
 k-=1 
if k==0:
 print(0)
else:
 half_k=k>>1
 prices=[]
 for _ in range(n):
  prices.append(int(input()))
 minimi=[[0 for _ in range(n)] for _ in range(n)]
 for i in range(n):
  for j in range(i,n):
   if i==j:
    minimi[i][j]=prices[j]
   else:
    minimi[i][j]=min(minimi[i][j-1], prices[j])
 tabella=[[0 for _ in range(n)] for _ in range(half_k)]
 for j in range(1,n):
  tabella[0][j]=max(prices[j]-minimi[0][j-1], tabella[0][j-1])
 for i in range(1,half_k):
  for j in range(1,n):
   tabella[i][j]=max(tabella[i][j-1], tabella[i-1][j])
   appo=0
   for k in range(j-1):
    appo=max(appo, tabella[i-1][k]+prices[j]-minimi[k+1][j-1])
   tabella[i][j]=max(tabella[i][j], appo)
 print(tabella[-1][-1])

# cook your dish here
try:
 n,k = map(int,input().split())
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass

try:
 n,k = list(map(int,input().split()))
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass


try:
 n,k = list(map(int,input().split()))
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass


# N,K = input().split() #N is the number of days    #K is the number of visits
# N = int(N)
# K = int(K)

# cook your dish here
# stock buy/sell to maximize profit
try:
 n,k = map(int,input().split())
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass

# cook your dish here
def max_profit(prices,n,k):

 profit = [[0 for i in range(n)] for j in range(k+1)] 
 for i in range(1,k+1):

  diff = (-1)*prices[0]
  for j in range(1,n):
   diff = max(profit[i-1][j]-prices[j],diff)
   profit[i][j] = max(profit[i][j-1],diff+prices[j])
 
 return profit[k][n-1]
 
try:
 n,k = map(int,input().split())
 prices = [int(input()) for _ in range(n)]
 print(max_profit(prices,n,k//2))

except:
 pass

# cook your dish here
n,k=map(int,input().split())
k=k//2
l = []
for _ in range(n):
 l.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]

 #print("pr bef:\n",pr)
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):

   #print("\ni,j:",i,j,"\ncomparing:pd",pd,"--and pr[i-1][j-1]  - p[j                -1]",pr[i-1][j-1],"-",p[j-1])
   pd=max(pd,pr[i-1][j-1]-p[j-1])


   #print("pr[i][j] by comparing : pr[i][j-1],p[j]+pd ka max:",pr[i][j                -1],p[j],"+",pd)
   pr[i][j]=max(pr[i][j-1],p[j]+pd)

   #print("pr:",pr)



 #print("pr aft:\n",pr)
 return pr[k][n-1]
print(fip(l,n,k))

# cook your dish here
# stock buy/sell to maximize profit
try:
 n,k = map(int,input().split())
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass

n,k=map(int,input().split())
k=k//2
l = []
for _ in range(n):
 l.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]

 #print("pr bef:\n",pr)
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):

   #print("\ni,j:",i,j,"\ncomparing:pd",pd,"--and pr[i-1][j-1]  - p[j                -1]",pr[i-1][j-1],"-",p[j-1])
   pd=max(pd,pr[i-1][j-1]-p[j-1])


   #print("pr[i][j] by comparing : pr[i][j-1],p[j]+pd ka max:",pr[i][j                -1],p[j],"+",pd)
   pr[i][j]=max(pr[i][j-1],p[j]+pd)

   #print("pr:",pr)



 #print("pr aft:\n",pr)
 return pr[k][n-1]
print(fip(l,n,k))

n,k=map(int,input().split())
k=k//2
l = []
for _ in range(n):
 l.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]

 #print("pr bef:\n",pr)
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):

   #print("\ni,j:",i,j,"\ncomparing:pd",pd,"--and pr[i-1][j-1]  - p[j                -1]",pr[i-1][j-1],"-",p[j-1])
   pd=max(pd,pr[i-1][j-1]-p[j-1])


   #print("pr[i][j] by comparing : pr[i][j-1],p[j]+pd ka max:",pr[i][j                -1],p[j],"+",pd)
   pr[i][j]=max(pr[i][j-1],p[j]+pd)

   #print("pr:",pr)



 #print("pr aft:\n",pr)
 return pr[k][n-1]
print(fip(l,n,k))

n,k=map(int,input().split())
k=k//2
l = []
for _ in range(n):
 l.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]

 #print("pr bef:\n",pr)
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):

   #print("\ni,j:",i,j,"\ncomparing:pd",pd,"--and pr[i-1][j-1]  - p[j                -1]",pr[i-1][j-1],"-",p[j-1])
   pd=max(pd,pr[i-1][j-1]-p[j-1])


   #print("pr[i][j] by comparing : pr[i][j-1],p[j]+pd ka max:",pr[i][j                -1],p[j],"+",pd)
   pr[i][j]=max(pr[i][j-1],p[j]+pd)

   #print("pr:",pr)



 #print("pr aft:\n",pr)
 return pr[k][n-1]
print(fip(l,n,k))

# cook your dish here
# stock buy/sell to maximize profit
try:
 n,k = map(int,input().split())
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass

# cook your dish here
# stock buy/sell to maximize profit
try:
 n,k = map(int,input().split())
 x = [int(input()) for _ in range(n)]
 k = k//2
 dp = [0]*(k+1)
 for i in range(k+1):
  dp[i] = [0]*n
 #print(dp)
 for i in range(1,k+1):
  #print("*",dp[i-1][0])
  diff = (-1)*x[0]
  for j in range(1,n):
   diff = max(dp[i-1][j]-x[j],diff)
   dp[i][j] = max(dp[i][j-1],diff+x[j])
 print(dp[k][n-1])
except:
 pass

n,k=list(map(int,input().split()))
k=k//2
l=[]
d={}
for i in range(n):
 l.append(int(input()))
for i in range(k+1):
 d[i]=[0]*n
for i in range(1,k+1):
 maxdiff=d[i-1][0]-l[0]
 for j in range(1,n):
  maxdiff=max(d[i-1][j]-l[j],maxdiff)
  d[i][j]=max(d[i][j-1],maxdiff+l[j])
#print(d)
print(d[k][-1])



n,k=map(int,input().split())
k=k//2
l = []
for _ in range(n):
 l.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):
   pd=max(pd,pr[i-1][j-1]-p[j-1])
   pr[i][j]=max(pr[i][j-1],p[j]+pd)
 return pr[k][n-1]
print(fip(l,n,k))

n,k=map(int,input().split())
k=k//2
l = []
for _ in range(n):
 l.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):
   pd=max(pd,pr[i-1][j-1]-p[j-1])
   pr[i][j]=max(pr[i][j-1],p[j]+pd)
 return pr[k][n-1]
print(fip(l,n,k))

n,k=map(int,input().split())
k=k//2
l = []
for _ in range(n):
 l.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):
   pd=max(pd,pr[i-1][j-1]-p[j-1])
   pr[i][j]=max(pr[i][j-1],p[j]+pd)
 return pr[k][n-1]
print(fip(l,n,k))

# cook your dish here
n,k=list(map(int,input().split()))
li=[]
k=k//2
for i in range(n):
 li.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):
   pd=max(pd,pr[i-1][j-1]-p[j-1])
   pr[i][j]=max(pr[i][j-1],p[j]+pd)
 return pr[k][n-1]
print(fip(li,n,k))


# cook your dish here
n,k=list(map(int,input().split()))
li=[]
k=k//2
for i in range(n):
 li.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):
   pd=max(pd,pr[i-1][j-1]-p[j-1])
   pr[i][j]=max(pr[i][j-1],p[j]+pd)
 return pr[k][n-1]
print(fip(li,n,k))


n,k=list(map(int,input().split()))
li=[]
k=k//2
for i in range(n):
 li.append(int(input()))
def fip(p,no,kt):
 pr=[[0 for i in range(n+1)] for j in range(k+1)]
 for i in range(1,k+1):
  pd=float('-inf')
  
  for j in range(1,n):
   pd=max(pd,pr[i-1][j-1]-p[j-1])
   pr[i][j]=max(pr[i][j-1],p[j]+pd)
 return pr[k][n-1]
print(fip(li,n,k))