Best Time To Buy and Sell Stock Problem Statement

You are given an array 'PRICES' of 'N' integers, where 'PRICES[i]' represents the price of a certain stock on the i-th day. An integer 'K' is also provided, indicating the maximum number of transactions you can perform.

Your task is to determine the maximum profit achievable with at most K transactions. A valid transaction would require buying a stock before selling it.

Note:
    You cannot engage in multiple transactions simultaneously, meaning you must sell a stock before buying it again.

Example:

Input:
N = 6, PRICES = [3, 2, 6, 5, 0, 3], K = 2
Output:
7
Explanation:

The optimal method to achieve maximum profit is to buy on day 2 (price = 2) and sell on day 3 (price = 6), then rebuy on day 5 (price = 0) and sell on day 6 (price = 3). The total profit would thus be (6 - 2) + (3 - 0) = 7.

Input:

The first line of input contains an integer 'T' denoting the number of test cases.
For each test case, the first line provides two space-separated integers, 'N' and 'K'.
The second line of each test case contains 'N' space-separated integers denoting the 'PRICES' array.

Output:

For each test case, output a single integer representing the maximum profit possible with at most K transactions.
Provide the result for each test case on a new line.

Constraints:

  • 1 <= T <= 100
  • 1 <= N <= 5000
  • 0 <= K <= N/2
  • 0 <= PRICES[i] <= 105

Time Limit: 1 second

AnswerBot
4d

Find the maximum profit achievable with at most K transactions by buying and selling stocks.

  • Iterate through the array and keep track of the minimum price to buy and maximum profit for each transaction...read more

Help your peers!
Add answer anonymously...
Amazon Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter