计算机多媒体辅助教学网站开发,WordPress 文艺,淘宝推广费用一般多少,网站开发实验报告模版文章目录 题目链接#xff1a;题目描述#xff1a;解题思路一#xff08;贪心算法#xff09;#xff1a;解体思路二#xff08;动态规划#xff09;#xff1a; 题目链接#xff1a;
122.买卖股票的最佳时机II
题目描述#xff1a; 解题思路一#xff08;贪心算法… 文章目录 题目链接题目描述解题思路一贪心算法解体思路二动态规划 题目链接
122.买卖股票的最佳时机II
题目描述 解题思路一贪心算法 本问题可以通过贪心算法解决。我们可以将问题分解为一系列连续的上涨子序列并在每个上涨子序列中计算利润并将其累加到最终的结果中。具体的做法是 贪心算法的核心思想对于每个上升的子序列我们希望在价格上涨时不断买入价格下跌时卖出。连续上升子序列在遍历股票价格的过程中如果当前价格小于下一天的价格说明价格在上涨应该继续持有股票如果当前价格大于或等于下一天的价格说明我们已经遇到了一个下降的趋势在此时卖出计算当前区间的利润。利润计算每次找到一个上涨子序列时我们就将该子序列的利润即当前价格减去子序列的起始价格累加到总利润中。 复杂度分析
时间复杂度O(N)空间复杂度O(1)
代码实现方式一
找到每一个连续递增子序列将其差值作为利润记录到总利润中
class Solution {
public:int maxProfit(vectorint prices) {int p1 0;int p2 0;int res 0;int n prices.size();while(p2n-1){if(prices[p2] prices[p21]){p2;continue;}else{res res (prices[p2]-prices[p1]);p2;p1p2;}}return res(prices[p2]-prices[p1]);}
};代码实现方式2
每次遍历数组比较相邻的价格即 prices[i] 和 prices[i1]如果 prices[i1] prices[i]则说明价格上涨可以在今天买入明天卖出获得的利润是 prices[i1] - prices[i]。如果 prices[i1] prices[i]则不进行操作不获得任何利润。 利用 max(0, prices[i1] - prices[i]) 确保当价格下降时不加入负的利润。本质上与第一种方式一致但是这种实现方式更简洁
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();int res 0;for(int i0; in-1; i){res max(0, prices[i1]-prices[i]);}return res;}
};解体思路二动态规划
由于题目中要求在任何时候手里最多只有一支股票因此在每天交易完成后只可能手里有一支股票或者没有股票的状态
我们可以定义
dp[i][0] : 表示第i天交易完成后手里没有股票的最大利润i从0开始dp[i][1] : 表示第i天交易完成后手里持有一支股票的最大利润i从0开始
因此dp[i][0] 的转移方程如果这一天交易完成后手里没有股票那么可能的状态转移为前一天已经没有股票了即 dp[i-1][0],或者前一天结束的时候手里有一支股票即dp[i-1][1]这时候我们要将其卖出并获得prices[i]收益。因此为了利益最大化我们的状态转移方程 d p [ i ] [ 0 ] max ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] p r i c e s [ i ] ) dp[i][0] \max \left( dp[i-1][0], dp[i-1][1] prices[i] \right) dp[i][0]max(dp[i−1][0],dp[i−1][1]prices[i])
再来考虑dp[i][1]如果转移状态前一天已经持有一支股票。即dp[i-1][1]或者前一天结束的时候手里没有股票即dp[i-1][0]这时候我们要将其买入并减少prices[i]的收益。可以列出状态转移方程 d p [ i ] [ 1 ] max ( d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] , d p [ i − 1 ] [ 1 ] ) dp[i][1] \max \left( dp[i-1][0] - prices[i], dp[i-1][1] \right) dp[i][1]max(dp[i−1][0]−prices[i],dp[i−1][1])
对于初始状态我们直到在第0天交易结束的时候
dp[0][0] 0dp[0][1] -prices[0]
代码实现
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();int dp[n][2];dp[0][0] 0;dp[0][1] -prices[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][0]-prices[i], dp[i-1][1]);}return dp[n-1][0];}
};动态规划解析参考
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solutions/476791/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/?envTypestudy-plan-v2envIdtop-interview-150
