郑州做网站哪里便宜,芜湖网络公司,做网站多少钱西宁君博美评,在东莞找工作上哪个网站目录 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 121. 买卖股票的最佳时机 题目链接#xff1a;121. 买卖股票的最佳时机 比较好想到的是贪心算法#xff0c;贪心选择价格更低的日子买入#xff0c;价格更高的日子卖出。 class Solution {
public:int maxProfit(vec… 目录 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 121. 买卖股票的最佳时机 题目链接121. 买卖股票的最佳时机 比较好想到的是贪心算法贪心选择价格更低的日子买入价格更高的日子卖出。 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;}
}; 动态规划算法不太好想到 1dp[ i ][ 0 ] 表示第 i 天持有股票时手上的最大金额 dp[ i ][ 1 ] 表示第 i 天不持有股票时手上的最大金额 初始手上金额为 0持有股票说明当前已经买入了股票则手上金额为负 2dp[ i ][ 0 ] max( dp[ i - 1][ 0 ], -prices[ i ] ); dp[ i ][ 1 ] max( dp[ i - 1 ][ 1 ], dp[ i - 1 ][ 0 ] prices[ i ] ); 3dp[ 0 ][ 0 ] -prices[ i ]; dp[ 0 ][ 1 ] 0 4按天遍历 class Solution {
public:int maxProfit(vectorint prices) {vectorvectorint dp(2, vectorint(2, 0));// dp[i][0]表示第i天持有股票时手中的最大金额// dp[i][1]表示第i天不持股票时手中的最大金额dp[0][0] -prices[0];for(int i 1; i prices.size(); i){dp[i % 2][0] max(dp[(i-1) % 2][0], -prices[i]);dp[i % 2][1] max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] prices[i]);}return dp[(prices.size() - 1) % 2][1];}
}; 122.买卖股票的最佳时机II 题目链接122. 买卖股票的最佳时机 II 贪心算法之前做过了本题的动态规划方法就比较传统 1dp[ i ] 表示前 i 天能得到的最大利润 2dp[ i ] max( dp[ i - 1], dp[ i - 1 ] prices[ i ] - prices[ i - 1 ] ) 3dp[ 0 ] 0 4按天遍历 class Solution {
public:int maxProfit(vectorint prices) {vectorint dp(prices.size(), 0);dp[0] 0;for(int i 1; i prices.size(); i){dp[i] max(dp[i - 1], dp[i - 1] prices[i] - prices[i - 1]);}return dp[prices.size() - 1];}
};
