class Solution {
public:
int maxProfit(vector<int>& prices) {
}
};
309. 最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1] 输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000原站题解
rust 解法, 执行用时: 4 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-05 09:54:35
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut pre0 = 0;
let mut f0 = 0;
let mut f1 = i32::MIN;
for p in &prices {
let new_f0 = f0.max(f1 + p); // f[i+2][0]
f1 = f1.max(pre0 - p); // f[i+2][1]
pre0 = f0;
f0 = new_f0;
}
f0
}
}
javascript 解法, 执行用时: 72 ms, 内存消耗: 43.1 MB, 提交时间: 2023-10-05 09:54:19
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let pre0 = 0, f0 = 0, f1 = -Infinity;
for (let p of prices) {
[pre0, f0, f1] = [f0, Math.max(f0, f1 + p), Math.max(f1, pre0 - p)];
}
return f0;
};
javascript 解法, 执行用时: 48 ms, 内存消耗: 43.1 MB, 提交时间: 2023-10-05 09:54:06
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
const n = prices.length;
const memo = new Array(n).fill(null).map(() => [-1, -1]); // -1 表示没有计算过
function dfs(i, hold) {
if (i < 0) {
return hold ? -Infinity : 0;
}
if (memo[i][hold] !== -1) { // 之前计算过
return memo[i][hold];
}
let res;
if (hold) {
res = Math.max(dfs(i - 1, 1), dfs(i - 2, 0) - prices[i]);
} else {
res = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
}
return memo[i][hold] = res; // 记忆化
}
return dfs(n - 1, 0);
};
rust 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2023-10-05 09:53:46
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let n = prices.len();
let mut memo = vec![vec![-1; 2]; n]; // -1 表示还没有计算过
fn dfs(idx: i32, hold: bool, prices: &Vec<i32>, memo: &mut Vec<Vec<i32>>) -> i32 {
if idx < 0 {
if hold {
return i32::MIN;
}
return 0;
}
let i = idx as usize;
let j = hold as usize;
if memo[i][j] != -1 { // 之前计算过
return memo[i][j];
}
let res;
if hold {
res = dfs(idx - 1, true, prices, memo).max(dfs(idx - 2, false, prices, memo) - prices[i]);
} else {
res = dfs(idx - 1, false, prices, memo).max(dfs(idx - 1, true, prices, memo) + prices[i]);
}
memo[i][j] = res; // 记忆化
res
}
dfs(n as i32 - 1, false, &prices, &mut memo)
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-05 09:53:14
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
n := len(prices)
// f[i][0]: 手上持有股票的最大收益
// f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
// f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
f := make([][3]int, n)
f[0][0] = -prices[0]
for i := 1; i < n; i++ {
f[i][0] = max(f[i-1][0], f[i-1][2] - prices[i])
f[i][1] = f[i-1][0] + prices[i]
f[i][2] = max(f[i-1][1], f[i-1][2])
}
return max(f[n-1][1], f[n-1][2])
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.8 MB, 提交时间: 2023-10-05 09:53:00
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
# f[i][0]: 手上持有股票的最大收益
# f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
# f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
f = [[-prices[0], 0, 0]] + [[0] * 3 for _ in range(n - 1)]
for i in range(1, n):
f[i][0] = max(f[i - 1][0], f[i - 1][2] - prices[i])
f[i][1] = f[i - 1][0] + prices[i]
f[i][2] = max(f[i - 1][1], f[i - 1][2])
return max(f[n - 1][1], f[n - 1][2])
cpp 解法, 执行用时: 0 ms, 内存消耗: 11.2 MB, 提交时间: 2023-10-05 09:52:26
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) {
return 0;
}
int n = prices.size();
int f0 = -prices[0];
int f1 = 0;
int f2 = 0;
for (int i = 1; i < n; ++i) {
int newf0 = max(f0, f2 - prices[i]);
int newf1 = f0 + prices[i];
int newf2 = max(f1, f2);
f0 = newf0;
f1 = newf1;
f2 = newf2;
}
return max(f1, f2);
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.6 MB, 提交时间: 2023-10-05 09:52:11
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
int f0 = -prices[0];
int f1 = 0;
int f2 = 0;
for (int i = 1; i < n; ++i) {
int newf0 = Math.max(f0, f2 - prices[i]);
int newf1 = f0 + prices[i];
int newf2 = Math.max(f1, f2);
f0 = newf0;
f1 = newf1;
f2 = newf2;
}
return Math.max(f1, f2);
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-05 09:51:56
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
f0, f1, f2 = -prices[0], 0, 0
for i in range(1, n):
newf0 = max(f0, f2 - prices[i])
newf1 = f0 + prices[i]
newf2 = max(f1, f2)
f0, f1, f2 = newf0, newf1, newf2
return max(f1, f2)
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2021-07-23 11:00:01
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
n := len(prices)
//f0: 第一天结束手里有股票
//f1: 第一天结束无股票, 不处于冷冻期
//f2: 第一天结束无股票, 冷冻期
f0, f1, f2 := -prices[0], 0, 0
for i := 1; i < n; i++ {
newf0 := max(f0, f2 - prices[i])
newf1 := f0 + prices[i]
newf2 := max(f1, f2)
f0, f1, f2 = newf0, newf1, newf2
}
return max(f1, f2)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}