百度网站建设流程,徐州模板网站托管平台,国内建筑网站,线上问诊网站建设文章目录 单只股票买卖多次买卖单只股票最多两次买卖股票最多买k次含冷静期含手续费 单只股票买卖
买卖股票的最佳时机 关键思路#xff1a;找到一个值#xff0c;他与之后的最大值之差最大。 用minprice记录最小的值#xff0c;用maxprofit记录最大的收益。 想清楚一个点… 文章目录 单只股票买卖多次买卖单只股票最多两次买卖股票最多买k次含冷静期含手续费 单只股票买卖
买卖股票的最佳时机 关键思路找到一个值他与之后的最大值之差最大。 用minprice记录最小的值用maxprofit记录最大的收益。 想清楚一个点
更新最小值时影响最大收益吗 不会影响因为每个收益都是需要根据minprice后续的最大值
class Solution {public int maxProfit(int[] prices) {if(prices.length1) return 0;int n prices.length;int minprice Integer.MAX_VALUE;int maxprofit 0;for(int i 0 ; i n ;i ){minprice Math.min(minprice, prices[i]);maxprofit Math.max(prices[i] -minprice,maxprofit);}return maxprofit;}
}多次买卖单只股票
买卖股票的最佳时机 II profitBuy 用于记录已购买股票后的最大利润而 profitNOBuy 用于记录未购买股票时的最大利润。在一个循环中它逐步计算了每一天的最佳策略然后返回最后一天的最大利润。
profitBuy[i] 表示在第 i 天持有股票时的最大利润它等于在第 i-1 天继续持有股票或在第 i-1 天卖出股票后买入的最大值。profitNOBuy[i] 表示在第 i 天没有持有股票时的最大利润它等于在第 i-1 天继续观望不购买股票或在第 i-1 天购买股票后卖出的最大值。
在遍历结束后函数返回两种情况的最大值即最大利润。用动态规划的方法来解决买卖股票的问题确保在每一天都选择最优的策略以获得最大的利润。
class Solution {public int maxProfit(int[] prices) {int n prices.length;int profitBuy[] new int[n]; // 用于记录已购买股票后的最大利润int profitNOBuy[] new int[n]; // 用于记录未购买股票时的最大利润profitBuy[0] -prices[0]; // 初始化第一天已购买的情况初始资金为负的第一天股票价格profitNOBuy[0] 0; // 初始化第一天未购买股票的情况初始资金为0for (int i 1; i n; i) {// 更新已购买股票后的最大利润考虑继续持有或卖出的情况profitBuy[i] Math.max(profitBuy[i - 1], profitNOBuy[i - 1] - prices[i]);// 更新未购买股票时的最大利润考虑继续观望或购买的情况profitNOBuy[i] Math.max(profitNOBuy[i - 1], profitBuy[i - 1] prices[i]);}// 最终返回最后一天的两种情况的最大值即最大利润return Math.max(profitBuy[n - 1], profitNOBuy[n - 1]);}
}
最多两次买卖股票
123. 买卖股票的最佳时机 III
首先定义了四个变量minpricemaxprofitminprice2和maxprofit2它们用来存储在遍历价格数组过程中的一些重要信息。通过循环遍历价格数组 prices其中 i 表示当前的天数。minprice 用来记录在第 i 天之前的最低股票价格。在循循环过程中不断更新 minprice 为当前价格 prices[i] 和 minprice 之间的较小值。maxprofit 用来记录在第 i 天卖出股票时的最大利润。利润计算为当前价格 prices[i] 减去之前的最低价格 minprice并且与之前的最大利润 maxprofit 比较取较大值。minprice2 用来记录在第 i 天之前的最低股票价格考虑到第二次交易。这里 minprice2 考虑了第一次交易的收益 maxprofit即 prices[i] - maxprofit因为在第一次交易中你已经卖出了一次股票所以要减去第一次交易的利润。maxprofit2 用来记录在第 i 天卖出股票时的最大利润考虑第二次交易。利润计算为当前价格 prices[i] 减去之前的最低价格 minprice2并与之前的最大利润 maxprofit2 比较取较大值。最后返回 Math.max(maxprofit2, maxprofit)因为你要最大化两次交易的总利润。
这个算法的关键在于动态地维护四个变量以确保在每一天都考虑了两次交易的情况并计算出最大利润。
class Solution {public int maxProfit(int[] prices) {int n prices.length;if(n1) return 0;int minprice Integer.MAX_VALUE;int maxprofit 0;int minprice2 Integer.MAX_VALUE;int maxprofit2 0;for(int i 0 ; i n ;i ){minprice Math.min(minprice, prices[i]);minprice2 Math.min(minprice2 , prices[i] - maxprofit);maxprofit Math.max(prices[i] -minprice,maxprofit);maxprofit2 Math.max(maxprofit2 , prices[i] - minprice2);}return Math.max(maxprofit2,maxprofit);}
}最多买k次
188. 买卖股票的最佳时机 IV 把k想象成2即可按照两次的思路
class Solution {public int maxProfit(int k, int[] prices) {int n prices.length;if(n1) return 0;int minprice[] new int[k];int maxprofit[] new int[k];for(int i0;ik;i){minprice[i] Integer.MAX_VALUE;maxprofit[i] 0;}for(int i 0 ; i n ;i ){minprice[0] Math.min(minprice[0], prices[i]);maxprofit[0] Math.max(prices[i] -minprice[0],maxprofit[0]); for(int j1;jk;j){minprice[j] Math.min(minprice[j] , prices[i] - maxprofit[j-1]); maxprofit[j] Math.max(maxprofit[j] , prices[i] - minprice[j]);}}return maxprofit[k-1];}
}含冷静期
309. 买卖股票的最佳时机含冷冻期
状态转移图
class Solution {public int maxProfit(int[] prices) {int n prices.length;if(n1) return 0;int dpNoBuy[] new int[n];int dpBuy[] new int[n];int dpCd[] new int[n];dpNoBuy[0] -prices[0];dpBuy[0] 0;dpCd[0] 0;for (int i 1; i n; i ) {dpNoBuy[i] Math.max(dpCd[i-1] - prices[i],dpNoBuy[i-1]);dpBuy[i] Math.max(dpNoBuy[i-1] prices[i],dpBuy[i-1]);dpCd[i] Math.max(dpCd[i-1],dpBuy[i-1]);}return Math.max(Math.max(dpNoBuy[n-1],dpCd[n-1]),dpBuy[n-1]);}
}含手续费
714. 买卖股票的最佳时机含手续费 两个状态转换即可 class Solution {public int maxProfit(int[] prices, int fee) {int n prices.length;if(n1) return 0;int buy[] new int[n];int sell[] new int[n];buy[0] -prices[0];sell[0] 0;for(int i 1;in;i){buy[i] Math.max(buy[i-1],sell[i-1]-prices[i]);sell[i] Math.max(sell[i-1],buy[i]prices[i]-fee);}return Math.max(buy[n-1],sell[n-1]);}
}
