Morgan Stanley OA-1 2022

Problem Description

In the online reselling app, Keeto, vendors can resell items with fluctuating prices. A vendor can buy an item on one day and sell it on any subsequent day, but they must sell any previously owned item before purchasing a new one. Your task is to determine the maximum profit a vendor can achieve with at most K transactions, where each transaction consists of a purchase followed by a sale.

Given the prices of an item over N days, you need to develop an algorithm that calculates the maximum profit for the vendor with the constraint of at most K transactions.

Input Format

• The first line contains an integer N — the number of days for which the item prices are given.
• The second line contains N space-separated integers representing the price of the item on each day.
• The third line contains an integer K — the maximum number of transactions allowed.

Output Format

• Print a single integer representing the maximum profit a vendor can earn from buying and selling the items with at most K transactions.

Constraints

• 0 <= K < N <= 500
• 0 <= price[i] <= 10^9 for (0 <= i < N)

Sample Input

6
5 20 10 30 50 70
2

Sample Output

75