当前位置:网站首页>LeetCode Question of the Day (309. Best Time to Buy and Sell Stock with Cooldown)
LeetCode Question of the Day (309. Best Time to Buy and Sell Stock with Cooldown)
2022-08-01 05:48:00 【wangjun861205】
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1]
Output: 0
Constraints:
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
当 prices[i] >= prices[i-1]的时候, 我们有两个选择, One is to sell the current stock, 然后跳到 i+2(because after the sale 1 天的冷静期), The other is not for sale, then walk normally i+1. We maintain both the current maximum and minimum prices, Similar to a monotonically increasing queue, Used to record the current best buying time and best selling time
use std::collections::HashMap;
impl Solution {
fn dp(
prices: &Vec<i32>,
i: usize,
min: i32,
max: i32,
cache: &mut HashMap<(usize, i32, i32), i32>,
) -> i32 {
if i >= prices.len() {
return max - min;
}
let curr = prices[i];
if min == -1 && max == -1 {
let ans = if let Some(c) = cache.get(&(i + 1, curr, curr)) {
*c
} else {
Solution::dp(prices, i + 1, curr, curr, cache)
};
cache.insert((i, -1, -1), ans);
return ans;
}
if curr >= max {
let sell = if let Some(c) = cache.get(&(i + 2, -1, -1)) {
*c
} else {
Solution::dp(prices, i + 2, -1, -1, cache)
} + curr
- min;
let keep = if let Some(c) = cache.get(&(i + 1, min, max)) {
*c
} else {
Solution::dp(prices, i + 1, min, max, cache)
};
let ans = sell.max(keep);
cache.insert((i, min, max), ans);
return ans;
}
if curr <= min {
let ans = if let Some(c) = cache.get(&(i + 1, curr, curr)) {
*c
} else {
Solution::dp(prices, i + 1, curr, curr, cache)
};
cache.insert((i, min, max), ans);
return ans;
} else {
let ans = if let Some(c) = cache.get(&(i + 1, min, curr)) {
*c
} else {
Solution::dp(prices, i + 1, min, curr, cache)
};
cache.insert((i, min, max), ans);
return ans;
}
}
pub fn max_profit(prices: Vec<i32>) -> i32 {
Solution::dp(&prices, 0, -1, -1, &mut HashMap::new())
}
}
边栏推荐
猜你喜欢
WPF项目-初步了解数据绑定 binding
企业员工人事管理系统(数据库课设)
JWL-11/2-99.9A电流继电器
对于升级go1.18的goland问题
【MySQL必知必会】 表的优化 | 充分利用系统资源
从离线到实时对客,湖仓一体释放全量数据价值
Dialogue with the father of MySQL: One excellent programmer is worth 5 ordinary programmers
使用string 容器翻转 字母
leetcode125 验证回文串
Motion analysis and parameter optimization of crank-slider mechanism
随机推荐
从底层结构开始学习FPGA(6)----分布式RAM(DRAM,Distributed RAM)
The sword refers to Offer 68 - I. Nearest Common Ancestor of Binary Search Trees
Selenium: Popup Handling
对话MySQL之父:一个优秀程序员可抵5个普通程序员
类神经网络训练不起来怎么办
滚动条样式修改
uva10825
小白的0基础教程SQL: 关系数据库概述 02
Selenium: Element wait
【视觉SLAM十四讲】第一章理论详解
2022.7.26 Mock Competition
从零开始—仿牛客网讨论社区项目(一)
基于MATLAB的BP神经网络进行语音特征信号分类
Selenium:元素判断
小白的0基础教程SQL: 安装MYSQL 03
The BP neural network based on MATLAB voice characteristic signal classification
leetcode43 string multiplication
【FiddlerScript】利用FiddlerScript抓包保利威下载
crypto-js使用
解决浏览器滚动条导致的页面闪烁问题