学校资源网站的建设方案,企业推广策略,wordpress侧边栏 菜单,有限公司 官网前言
早上练车去了#xff08;好久没有8点前醒了#xff09;#xff0c;练科目二两小时下来脚根可真酸啊#xff0c;希望下周一把过。练完顺带去Apple西湖免费换新了耳机#xff0c;羊毛爽#xff01;
121. 买卖股票的最佳时机 - 力扣#xff08;LeetCode#xff09;…前言
早上练车去了好久没有8点前醒了练科目二两小时下来脚根可真酸啊希望下周一把过。练完顺带去Apple西湖免费换新了耳机羊毛爽
121. 买卖股票的最佳时机 - 力扣LeetCode 贪心法 更新最小值更新最大区间利润值 class Solution {
public:int maxProfit(vectorint prices) {int low INT_MAX;int result 0;for (int i 0; i prices.size(); i) {low min(low, prices[i]); // 取最左最小价格result max(result, prices[i] - low); // 直接取最大区间利润}return result;}
}; 动规法一维 一维思路和贪心类似有点难理解dp[i]含义 以prices[i]价格卖出可获得的最大利润 递推公式 情况一i-1买入i卖出收益prices[i] - prices[i-1]情况二i-1之前已卖出如果延迟到i卖出取更高的收益dp[i] max(prices[i] - prices[i-1], prices[i] - prices[i-1] dp[i-1]);初始化及顺序 dp[0] 0从前往后要最高收益结果取dp[i]的最大值和其他一维有差别另外可以优化一下空间 // 优化前
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorint dp(len);int result 0;for(int i 1; i len; i){dp[i] max(prices[i] - prices[i - 1], prices[i] - prices[i - 1] dp[i - 1]);result max(result, dp[i]);}return result;}
};// 优化后
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();int dp0 0, dp1 0; // 只需要维护滚动两个值int result 0;for(int i 1; i len; i){dp1 max(prices[i] - prices[i - 1], prices[i] - prices[i - 1] dp0);result max(result, dp1);dp0 dp1; // 互换}return result;}
};动规法二维 二维用的01双状态类似打家劫舍IIIdp数组含义 dp[i][0] 表示第i天持有股票所得最多现金维持现状 买入股票dp[i][1] 表示第i天不持有股票所得最多现金维持现状 卖出股票递推公式 dp[i][0] max(dp[i - 1][0], -prices[i]);dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);初始化及顺序 dp[0][0] -prices[0]; dp[0][1] 0; 从前往后答案取dp[max][1]因为不持有一定比持有多 class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(len, vectorint(2));dp[0][0] - prices[0];for(int i 1; i len; i){// 持有原状 买入dp[i][0] max(dp[i - 1][0], -prices[i]);// 不持有原状 卖出持有dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]);} return dp[len - 1][1];}
};
后言 先到这饿了看评论区尝试了一下一维和改进废了些时间晚上有空继续刷股票
