AlgoViz Lab交互式算法学习Algorithms first
买卖股票的最佳时机 III · 交互式算法学习
最多完成两笔交易，求最大利润。
#123 · 多维动态规划
买卖股票的最佳时机 III
Best Time to Buy and Sell Stock III
prices = [3,3,5,0,0,3,1,4]状态流3 个关键状态
步骤 1价格 3 初始化 buy1、buy2。
buy1=-3,buy2=-3状态 13
→状态 23
→状态 35
→状态 40
→状态 50
→状态 63
→状态 71
→状态 84
推荐
四个交易状态
时间
O(n)空间 O(1)依次维护第一次买入、第一次卖出、第二次买入、第二次卖出后的最大现金。
1function maxProfit(p) {2 let buy1 = -Infinity,3 sell1 = 0,4 buy2 = -Infinity,5 sell2 = 0;6 for (const x of p) {7 buy1 = Math.max(buy1, -x);8 sell1 = Math.max(sell1, buy1 + x);9 buy2 = Math.max(buy2, sell1 - x);10 sell2 = Math.max(sell2, buy2 + x)11 }12 return sell2;13}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public int maxProfit(int[] prices) {3 // 第一次买入，第一次卖出，第二次买入，第二次卖出4 int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;5 for (int i = 1; i < prices.length; ++i) {6 f1 = Math.max(f1, -prices[i]);7 f2 = Math.max(f2, f1 + prices[i]);8 f3 = Math.max(f3, f2 - prices[i]);9 f4 = Math.max(f4, f3 + prices[i]);10 }11 return f4;12 }13}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
买卖股票的最佳时机 III · 解法对比
最多完成两笔交易，求最大利润。
- 测试用例
prices = [3,3,5,0,0,3,1,4]- 题目分类
- 多维动态规划
- 解法对比
- 2
枚举分割点做两次单交易
把每一天作为两笔交易分界，左右各求一次最大单交易利润。
- 时间
O(n²)- 空间
O(1)
四个交易状态
依次维护第一次买入、第一次卖出、第二次买入、第二次卖出后的最大现金。
- 时间
O(n)- 空间
O(1)