Best time to buy and sell stock iv

Array Dynamic Programming

49.6% acceptance

Jan 12, 2026

7977

226

You are given an integer array prices where prices[i] is the price of a given stock on the ith 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).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
    if prices.is_empty() || k == 0 {
      return 0;
    }
    
    let n = prices.len();
    let k = k as usize;
    
    if k >= n / 2 {
      return prices.windows(2).map(|w| (w[1] - w[0]).max(0)).sum();
    }
    
    let mut buy = vec![i32::MIN; k + 1];
    let mut sell = vec![0; k + 1];
    
    for price in prices {
      for j in (1..=k).rev() {
        sell[j] = sell[j].max(buy[j] + price);
        buy[j] = buy[j].max(sell[j - 1] - price);
      }
    }
    
    sell[k]
  }
}