Morgan Stanley OA 2022 - Maximize Reselling Profit with Limited Transactions

Problem Description

An online reselling app, Keeto, allows vendors to resell items online to their customers. The prices of the items can fluctuate daily. The vendor can purchase an item on one day and sell it on any subsequent day. However, before buying a new item, the vendor must sell any previous item they own. Your task is to analyze the price fluctuations and calculate the maximum profit a vendor can earn from at most K transactions. One transaction consists of a purchase and a sale of an item.

Given the prices of an item over N days, write an algorithm to find the maximum profit the vendor can earn with 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