All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

MI vs CSK and Pearls
Tag(s):

Easy

Problem
Editorial
Analytics

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\)
SAMPLE INPUT
3 1
1 2 4
SAMPLE OUTPUT
3

Explanation

Paras can buy one pearl on the first day and can sell the pearl on either second day or last day

if Paras buys the pearl on first day and sell it on the last day he will get a maximum profit of 3.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?