企业官网建设流程全解析

网站文字编辑怎么做,国外网站推广平台有哪些公司,茂名专业网站建设,app简易开发平台题目描述 给你一个整数数组 prices#xff0c;其中 prices[i] 是第 i 天股票的价格#xff0c;以及一个整数 k。 你最多可以进行 k 笔交易#xff0c;每笔交易可以是以下任一类型#xff1a; 普通交易#xff08;做多#xff09;#xff1a;在第 i 天买入#xff0c…题目描述给你一个整数数组prices其中prices[i]是第 i 天股票的价格以及一个整数k。你最多可以进行k 笔交易每笔交易可以是以下任一类型普通交易做多在第 i 天买入然后在之后的第 j 天卖出i j。利润 prices[j] - prices[i]做空交易在第 i 天卖出然后在之后的第 j 天买回i j。利润 prices[i] - prices[j]限制条件必须在开始下一笔交易前完成当前交易不能在同一天进行多次买入或卖出操作返回可以获得的最大总利润。示例示例 1:输入: prices [1,7,9,8,2], k 2 输出: 14 解释: - 普通交易第 0 天买入(1)第 2 天卖出(9)利润 8 - 做空交易第 3 天卖出(8)第 4 天买回(2)利润 6 - 总利润 8 6 14示例 2:输入: prices [12,16,19,19,8,1,19,13,9], k 3 输出: 36 解释: - 普通交易买入(12)卖出(19)利润 7 - 做空交易卖出(19)买回(8)利润 11 - 普通交易买入(1)卖出(19)利润 18 - 总利润 7 11 18 36解题思路问题分析这道题的关键点在于支持两种交易类型做多和做空交易之间不能重叠必须先结束一笔再开始下一笔需要找到最优的 k 笔交易组合状态定义使用三维 DP 数组dp[i][j][s]i当前是第 i 天0 ≤ i nj已完成的交易数0 ≤ j ≤ ks当前状态s 0空仓不持有任何头寸s 1做多持有已买入等待卖出s 2做空持有已卖出等待买回dp[i][j][s]表示第 i 天、完成 j 笔交易、处于状态 s 时的最大收益。状态转移方程1. 空仓状态dp[i][j][0]可以从以下状态转移而来保持空仓dp[i-1][j][0]做多平仓卖出dp[i-1][j][1] prices[i]完成第 j 笔交易做空平仓买回dp[i-1][j][2] - prices[i]完成第 j 笔交易dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j][1] prices[i], dp[i-1][j][2] - prices[i])注意平仓操作会完成一笔交易所以从j状态平仓。2. 做多持有状态dp[i][j][1]可以从以下状态转移而来继续持有dp[i-1][j][1]今天买入dp[i-1][j-1][0] - prices[i]开始新交易dp[i][j][1] max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])注意开始新交易时从j-1的空仓状态转移因为这笔交易还未完成。3. 做空持有状态dp[i][j][2]可以从以下状态转移而来继续持有dp[i-1][j][2]今天卖空dp[i-1][j-1][0] prices[i]开始新交易dp[i][j][2] max(dp[i-1][j][2], dp[i-1][j-1][0] prices[i])初始化第 0 天的状态dp[0][0][0] 0初始空仓收益为 0dp[0][j][1] -prices[0]第 0 天买入成本为负dp[0][j][2] prices[0]第 0 天卖空收益为正对于所有j ∈ [1, k]都初始化持有状态这样可以简化边界处理。最终答案dp[n-1][k][0]最后一天、完成 k 笔交易、空仓状态的最大收益。代码实现funcmaximumProfit(prices[]int,kint)int64{n:len(prices)dp:make([][][]int64,n)fori:rangedp{dp[i]make([][]int64,k1)forj:rangedp[i]{dp[i][j]make([]int64,3)}}// 初始化第 0 天的状态forj:1;jk;j{dp[0][j][1]int64(-prices[0])dp[0][j][2]int64(prices[0])}fori:1;in;i{forj:1;jk;j{dp[i][j][0]max(dp[i-1][j][0],max(dp[i-1][j][1]int64(prices[i]),dp[i-1][j][2]-int64(prices[i])))dp[i][j][1]max(dp[i-1][j][1],dp[i-1][j-1][0]-int64(prices[i]))dp[i][j][2]max(dp[i-1][j][2],dp[i-1][j-1][0]int64(prices[i]))}}returndp[n-1][k][0]}funcmax(a,bint64)int64{ifab{returna}returnb}复杂度分析时间复杂度O(n × k)需要遍历 n 天每天处理 k 个交易数状态每个状态的转移是 O(1)空间复杂度O(n × k)DP 数组大小为 n × (k1) × 3空间优化可以使用滚动数组优化只保留前一天的状态将空间复杂度降到 O(k)funcmaximumProfit(prices[]int,kint)int64{n:len(prices)prev:make([][]int64,k1)curr:make([][]int64,k1)forj:0;jk;j{prev[j]make([]int64,3)curr[j]make([]int64,3)}forj:1;jk;j{prev[j][1]int64(-prices[0])prev[j][2]int64(prices[0])}fori:1;in;i{forj:1;jk;j{curr[j][0]max(prev[j][0],max(prev[j][1]int64(prices[i]),prev[j][2]-int64(prices[i])))curr[j][1]max(prev[j][1],prev[j-1][0]-int64(prices[i]))curr[j][2]max(prev[j][2],prev[j-1][0]int64(prices[i]))}prev,currcurr,prev}returnprev[k][0]}关键要点总结区分做多和做空必须用两个不同的状态来表示因为它们的收益计算方式不同做多买入负收益→ 卖出正收益做空卖出正收益→ 买回负收益交易完成时机从持有状态转到空仓状态时才算完成一笔交易交易数 1初始化技巧对所有 j 都初始化持有状态避免复杂的边界判断状态转移简洁用嵌套max函数一行代码表达所有可能的转移易错点❌ 试图用绝对值统一处理做多和做空 → 无法正确追踪状态转移❌ 交易数计数错位 → 应该在平仓时完成交易而非开仓时❌ 初始化不完整 → 导致某些状态无法转移相关题目LeetCode 121. 买卖股票的最佳时机k1只能做多LeetCode 122. 买卖股票的最佳时机 IIk∞LeetCode 123. 买卖股票的最佳时机 IIIk2只能做多LeetCode 188. 买卖股票的最佳时机 IV通用 k只能做多本题是最通用的版本同时支持做多和做空难度更高。