网站制作先学什么,公众号里的网站怎么做,淘宝直通车推广怎么做,网站做二维码吗2023.8.20 本题用dp算法做#xff0c;dp[i]的含义#xff1a;前 i1天能获得的最大利润。 然后每次循环时需要维护一个最小值min_num #xff1a;即 i1天中股票的最低价。剩下的步骤都很常规#xff0c;代码如下#xff1a;
一维dp#xff1a;
class Solution {
public:…2023.8.20 本题用dp算法做dp[i]的含义前 i1天能获得的最大利润。 然后每次循环时需要维护一个最小值min_num 即 i1天中股票的最低价。剩下的步骤都很常规代码如下
一维dp
class Solution {
public:int maxProfit(vectorint prices) {if(prices.size() 0) return 0;vectorint dp(prices.size());int min_num prices[0];dp[0] 0;for(int i1; iprices.size(); i){dp[i] max(dp[i-1] , prices[i]-min_num);min_num min(min_num , prices[i]);}return dp[prices.size()-1];}
}; 二维dp 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] , dp[i-1][0]prices[i]); 代码如下
class Solution {
public:int maxProfit(vectorint prices) {if(prices.size() 0) return 0;vectorvectorint dp(prices.size(),vectorint(2));dp[0][0] -prices[0];dp[0][1] 0;for(int i1; iprices.size(); 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[prices.size()-1][1];}
};
