Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 188 with 24 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 188 # by problem number
lcpy gen -s best_time_to_buy_and_sell_stock_iv # by problem name
prices where prices[i] is the price of a given stock on the i^th day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Input: k = 2, prices = [2,4,1]
Output: 2
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
class Solution:
# Time: O(n * min(k, n // 2))
# Space: O(min(k, n // 2))
def max_profit(self, k: int, prices: list[int]) -> int:
n = len(prices)
if n == 0:
return 0
# Each transaction uses at least two days, so more trades than n // 2
# degenerate into the unlimited-transaction case.
limit = min(k, n // 2)
buy = [-(10**9)] * (limit + 1)
sell = [0] * (limit + 1)
for price in prices:
for j in range(1, limit + 1):
buy[j] = max(buy[j], sell[j - 1] - price)
sell[j] = max(sell[j], buy[j] + price)
return sell[limit]
| Time | Space |
|---|---|
| O(n * min(k, n // 2)) | O(min(k, n // 2)) |