元隆盛建设集团有限公司网站,ps怎么下载永久免费版,网站建设相关标准,设计公司logo免费目录
力扣123. 买卖股票的最佳时机 III
状态机分析
解析代码 力扣123. 买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III
难度 困难
给定一个数组#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以…目录
力扣123. 买卖股票的最佳时机 III
状态机分析
解析代码 力扣123. 买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III
难度 困难
给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1:
输入prices [3,3,5,0,0,3,1,4]
输出6
解释在第 4 天股票价格 0的时候买入在第 6 天股票价格 3的时候卖出这笔交易所能获得利润 3-0 3 。随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3 。
示例 2
输入prices [1,2,3,4,5]
输出4
解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。 因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。示例 3
输入prices [7,6,4,3,1]
输出0
解释在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4
输入prices [1]
输出0提示
1 prices.length 1050 prices[i] 105
class Solution {
public:int maxProfit(vectorint prices) {}
}; 状态机分析 以某个位置为结尾结合题目要求定义一个状态表示 由于有买入和卖出可交易两个状态因此可以选择用两个数组。但是这道题里面还有交易次数的限制因此还需要再加上一维用来表示交易次数。其中
f[i][j] 表示第 i 天结束后完成了 j 次交易处于买入状态此时的最大利润g[i][j] 表示第 i 天结束后完成了 j 次交易处于卖出可交易状态此时的最大利润。
状态机 对于 f[i][j] 有两种情况到这个状态
在 i - 1 天的时候交易了 j 次处于买入状态第 i 天啥也不干即可。此时最大利润为 f[i - 1][j] ;在 i - 1 天的时候交易了 j 次处于卖出可交易状态第 i 天的时候把股票买了。此时的最大利润为 g[i - 1][j] - prices[i] 。
综上要的是最大利润因此是两者的最大值 f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]) ; 对于 g[i][j] 也有两种情况可以到达这个状态
在 i - 1 天的时候交易了 j 次处于卖出可交易状态第 i 天啥也不干即可。此时的最大利润为 g[i - 1][j] 在 i - 1 天的时候交易了 j - 1 次处于买入状态第 i 天把股票卖了然后就完成了 j 比交易。此时的最大利润为 f[i - 1][j - 1] prices[i] 。但是这个状态不⼀定存在要先判断⼀下。
综上我们要的是最大利润因此状态转移方程为
g[i][j] g[i - 1][j];
if(j - 1 0) g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]); 初始化、填表顺序、返回值 对于 f 表由于需要用到 i 0 时的状态因此初始化第一行即可。 当处于第 0 天的时候只能处于买入过一次的状态此时的收益为 -prices[0] 因此 f[0][0] - prices[0] 其它为负无穷。 对于 g 表由于需要用到 i 0 时的状态因此初始化第一行即可。 当处于第 0 天的时候处于卖出可交易状态啥也不干即可此时的收益为0 因此 f[0][0] 0其它为负无穷。 对于负无穷为了取 max 的时候⼀些不存在的状态起不到干扰的作用将它们初始化为负INF 用INT_MIN 在计算过程中会有溢出的风险这里 INF 折半取 0x3f3f3f3f 足够小即可。
填表顺序从左往右两个表一起填最后返回 g 表最后一行的最大值。 解析代码
class Solution {const int INF 0x3f3f3f3f;
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint f(n, vectorint(3, -INF)); // 最多两笔vectorvectorint g(n, vectorint(3, -INF));f[0][0] -prices[0];g[0][0] 0;for(int i 1; i n; i){for(int j 0; j 3; j){f[i][j] max(f[i-1][j], g[i-1][j] - prices[i]);g[i][j] g[i-1][j];if(j-1 0)g[i][j] max(g[i-1][j], f[i-1][j-1] prices[i]);}}return max(g[n-1][0], max(g[n-1][1], g[n-1][2]));}
};
