Practice/Oracle/Leetcode 188. Best Time to Buy and Sell Stock IV

Leetcode 188. Best Time to Buy and Sell Stock IV

CodingOptional

Problem

You are given an array of stock prices where prices[i] represents the price of a stock on day i, along with an integer k representing the maximum number of transactions you can complete.

A transaction consists of buying the stock on one day and selling it on a 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 using at most k transactions.

Requirements

1. Return the maximum profit achievable with at most k transactions
2. You must sell a stock before buying it again (no holding multiple stocks)
3. Handle the case where k is large enough that the limit doesn't matter
4. If no profit is possible, return 0

Constraints

• 1 ≤ k ≤ 100
• 1 ≤ prices.length ≤ 1000
• 0 ≤ prices[i] ≤ 1000

Examples

Example 1:

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

Example 2:

Input: k = 2, prices = [7, 6, 4, 3, 1] Output: 0 Explanation: No profitable transactions can be made as prices only decrease.

Example 3:

Input: k = 10, prices = [1, 2, 3, 4, 5] Output: 4 Explanation: With enough transactions allowed, capture every upward price movement: (2-1) + (3-2) + (4-3) + (5-4) = 4