aboutsummaryrefslogtreecommitdiff
path: root/buy_sell_stock.rs
blob: 268482f4198d3e2e50edc56b3b722ae9600ba436 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
use std::collections::HashMap;
struct Solution;

#[derive(PartialEq, Eq, Hash, Copy, Clone)]
enum Invested {
    Yes, No, Cooldown
}

impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        Self::dp(&prices, 0, Invested::No, &mut HashMap::new())
    }
    fn dp(prices: &[i32], day: usize, invested: Invested, memo: &mut HashMap<(usize, Invested), i32>) -> i32 {
        if day == prices.len() {
            0
        } else if let Some(profit) = memo.get(&(day, invested)) {
            *profit
        } else {
            let ans = match invested {
                Invested::Yes => Self::dp(prices, day + 1, invested, memo).max(prices[day] + Self::dp(prices, day + 1, Invested::Cooldown, memo)),
                Invested::No => Self::dp(prices, day + 1, invested, memo).max(-prices[day] + Self::dp(prices, day + 1, Invested::Yes, memo)),
                Invested::Cooldown => Self::dp(prices, day + 1, Invested::No, memo)
            };
            memo.insert((day, invested), ans);
            ans
        }
    }
}

fn main() {
    let prices = vec![1,2,3,0,2];
    print!("{}", Solution::max_profit(prices));
}