All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Vikram and Betal are very excited in watching IPL match of MI vs CSK. But problem is that Vikram is fan of MI and Betal is fan of CSK.So Betal uses his mind and asks Vikram that if he will give answer to his question then Betal will support MI otherwise Vikram will have to suport CSK for today's match. Betal's question is:-

As Paras is always interested in making money, so he decided to invest in some kind of precious pearls.But he is confused about when to buy and sell the pearl to get maximum profit.

He decided to give this work to you,

You have been given some future predictions of \(N\) days about the prices of the pearl in the form of an array \(A\), where the \(ith\) element denotes the price of the \(ith\) day.

Also, there is a restriction on the number of pearls you can buy or sell. You can sell or buy at most \(K\) pearls.And initially you are having zero pearls.

You have to find the maximum profit that can be made by buying and selling the pearls.

INPUT FORMAT

• The first line contains two integers \(N\) and \(K\).
• The second line contains \(N\) integers where ith integer denotes \(A_{i}\)  .

OUTPUT FORMAT

Print the maximum profit for each test case in a new line.

CONSTRAINTS

• \(1 \leq N \leq 10^5\)
• \(0\leq K \leq 10^5\)
• \(1\leq A[i] \leq 10^5\)