Practice/Meta/Leetcode 2291. Maximum Profit From Trading Stocks

Leetcode 2291. Maximum Profit From Trading Stocks

CodingOptional

Problem

You are given an array of stock prices where prices[i] represents the price of a stock on day i, and an integer budget that represents the maximum number of complete buy-sell transactions you can make.

A transaction consists of buying one share of stock on one day and selling it on a strictly later day. You cannot engage in multiple transactions simultaneously (you must sell the stock before you buy again).

Your goal is to determine the maximum profit you can achieve given the budget constraint on the number of transactions.

Requirements

1. You may complete at most budget transactions
2. You cannot hold more than one share of stock at a time (must sell before buying again)
3. A transaction is only complete when you both buy and sell
4. You can only sell stock on a day after you bought it
5. Return the maximum total profit achievable

Constraints

• 1 ≤ prices.length ≤ 1000
• 0 ≤ prices[i] ≤ 1000
• 1 ≤ budget ≤ 100
• Time complexity should be O(n * budget) or better
• Space complexity should be O(n * budget) or better

Examples

Example 1:

Input: prices = [3, 2, 6, 5, 0, 3], budget = 2 Output: 7 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 6), profit = 6-2 = 4. Then buy on day 4 (price = 0) and sell on day 5 (price = 3), profit = 3-0 = 3. Total profit = 4 + 3 = 7.

Example 2:

` Input: prices = [1, 3, 2, 8, 4, 9], budget = 4 Output: 13 Explanation: We can make 3 profitable transactions (budget allows 4):

• Buy at 1, sell at 3 (profit = 2)
• Buy at 2, sell at 8 (profit = 6)
• Buy at 4, sell at 9 (profit = 5) Total profit = 2 + 6 + 5 = 13. `

Example 3:

Input: prices = [5, 4, 3, 2, 1], budget = 3 Output: 0 Explanation: Prices only decrease, so no profitable transactions are possible.