中企动力网站案例,龙岗网站建设 公司推广,电脑云主机,黄石商城网站建设代码随想录算法训练营Day48 | 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II
LeetCode 121. 买卖股票的最佳时机
题目链接#xff1a;LeetCode 121. 买卖股票的最佳时机
思路#xff1a; 取左边最小#xff0c;更新右边最大。
class Solution {
public:int maxProf…代码随想录算法训练营Day48 | 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II
LeetCode 121. 买卖股票的最佳时机
题目链接LeetCode 121. 买卖股票的最佳时机
思路 取左边最小更新右边最大。
class Solution {
public:int maxProfit(vectorint prices) {int low INT_MAX;int result 0;for(int i0; iprices.size(); i){low min(low, prices[i]);result max(result, prices[i]-low);}return result;}
};//dpclass Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(n,vectorint(2));dp[0][0] -prices[0];dp[0][1] 0;for(int i1; in; 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[n-1][1];}
};注意
dp 分别为第i天没股票和第i天有股票的状态
LeetCode 122.买卖股票的最佳时机II
题目链接LeetCode 122.买卖股票的最佳时机II
思路 贪心简单
//贪心
class Solution {
public:int maxProfit(vectorint prices) {if(prices.size()1) return 0;int profit 0;for(int i1; iprices.size(); i){if(prices[i]prices[i-1]) profit prices[i]-prices[i-1];}return profit;}
};//dpclass Solution {
public:int maxProfit(vectorint prices) {if (prices.size()1) return 0;int n prices.size();vectorvectorint dp(n, vectorint(2));dp[0][0] -prices[0];dp[0][1] 0;for(int i1; in; i){dp[i][0] max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1] max(dp[i-1][1],dp[i-1][0]prices[i]);}return dp[n-1][1];}
};注意
dp同理
