Best time to buy and sell stock v

Array Dynamic Programming

60.8% acceptance

Feb 25, 2026

414

You are given prices array and integer k (at most k transactions). Normal transaction: buy day i, sell day j > i, profit = prices[j]-prices[i]. Short selling: sell day i, buy back day j > i, profit = prices[i]-prices[j]. Transactions cannot overlap. Return max total profit.

Solution

Rust

Time O(n * m)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_profit(prices: Vec<i32>, k: i32) -> i64 {
    let _n = prices.len();
    let k = k as usize;

    // DP: dp[t][i][state] = max profit using t transactions, on day i, in given state
    // state: 0=idle, 1=holding (bought, normal), 2=short (sold, waiting to rebuy)
    // Transitions:
    //   idle -> buy (start normal): dp[t][i+1][1] = max(dp[t][i][1], dp[t][i][0] - prices[i])
    //   holding -> sell: dp[t+1][i+1][0] = max(..., dp[t][i][1] + prices[i])  (completes 1 transaction)
    //   idle -> short sell: dp[t][i+1][2] = max(dp[t][i][2], dp[t][i][0] + prices[i])
    //   short -> rebuy: dp[t+1][i+1][0] = max(..., dp[t][i][2] - prices[i])
    //   idle stays idle, holding stays holding, short stays short (wait)
    
    // dp[t][state] updated as we scan days
    // t: number of COMPLETED transactions so far (0..=k)
    // Use rolling array over days

    const NEG_INF: i64 = i64::MIN / 2;
    // dp[t][s]: max profit with t completed transactions and state s
    let mut dp = vec![[NEG_INF; 3]; k + 1];
    dp[0][0] = 0; // 0 transactions, idle, 0 profit

    for &p in &prices {
      let p = p as i64;
      let mut ndp = vec![[NEG_INF; 3]; k + 1];
      for t in 0..=k {
        // state 0: idle
        if dp[t][0] != NEG_INF {
          // stay idle
          if ndp[t][0] < dp[t][0] { ndp[t][0] = dp[t][0]; }
          // start normal buy
          let v = dp[t][0] - p;
          if ndp[t][1] < v { ndp[t][1] = v; }
          // start short sell
          let v = dp[t][0] + p;
          if ndp[t][2] < v { ndp[t][2] = v; }
        }
        // state 1: holding normal
        if dp[t][1] != NEG_INF {
          // stay holding
          if ndp[t][1] < dp[t][1] { ndp[t][1] = dp[t][1]; }
          // sell (complete transaction)
          if t + 1 <= k {
            let v = dp[t][1] + p;
            if ndp[t + 1][0] < v { ndp[t + 1][0] = v; }
          }
        }
        // state 2: short
        if dp[t][2] != NEG_INF {
          // stay short
          if ndp[t][2] < dp[t][2] { ndp[t][2] = dp[t][2]; }
          // rebuy (complete transaction)
          if t + 1 <= k {
            let v = dp[t][2] - p;
            if ndp[t + 1][0] < v { ndp[t + 1][0] = v; }
          }
        }
      }
      dp = ndp;
    }

    let mut ans = 0i64;
    for t in 0..=k {
      if dp[t][0] > ans { ans = dp[t][0]; }
    }
    ans
  }
}