上海装饰公司网站建设,网站建设有哪几种形式,网站实名制 怎么做,南江红鱼洞水库建设管理局网站leetcode 121. 买卖股票的最佳时机 题目链接#xff1a;121. 买卖股票的最佳时机 - 力扣#xff08;LeetCode#xff09; 视频链接#xff1a;动态规划之 LeetCode#xff1a;121.买卖股票的最佳时机1_哔哩哔哩_bilibili 题目概述
给定一个数组 #xff0c;它的第 个元… leetcode 121. 买卖股票的最佳时机 题目链接121. 买卖股票的最佳时机 - 力扣LeetCode 视频链接动态规划之 LeetCode121.买卖股票的最佳时机1_哔哩哔哩_bilibili 题目概述
给定一个数组 它的第 个元素 表示一支给定股票第 天的价格。pricesiprices[i]i
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 。0 示例 1
输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。示例 2
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 没有交易完成, 所以最大利润为 0。
思路
1.确定dp数组含义
dp[i][0] 第i天持有股票所得最多现金。
dp[i][1] 第i天不持有股票所得最多现金。
这里的“持有”和“不持有”不代表当天买入股票或者卖出股票可能是前一天买的
2.确定递推公式(最开始现金为0元
第i天持有股票
1当天就买进股票-prices[i]
2前一天买进股票dp[i - 1][0]
所以dp[i][0] max(dp[i - 1][0], -prices[i])
第i天不持有股票
1当天卖出股票prices[i] dp[i - 1][0]
2前一天卖出股票dp[i - 1][1]
所以dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0])
3.数组初始化
dp[0][0] - prices[0]
dp[0][1] 0
4.确定遍历顺序
从前向后
5.打印dp数组 代码实现(动规)
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 i 1;i prices.size();i) {dp[i][0] max(-prices[i],dp[i - 1][0]);dp[i][1] max(prices[i] dp[i - 1][0],dp[i - 1][1]);} return dp[prices.size() - 1][1];}
};
代码实现(贪心)
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;}
}; leetcode 122.买卖股票的最佳时机II 题目链接122. 买卖股票的最佳时机 II - 力扣LeetCode 视频链接动态规划股票问题第二弹 | LeetCode122.买卖股票的最佳时机II_哔哩哔哩_bilibili 题目概述
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。 示例 1
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3 。总利润为 4 3 7 。
思路
本题和上一题没有多大区别唯一区别就是本题可以多次买卖在动规五部曲分析上也只有递归公式上有区别。
第i天持有股票
1当天就买进股票dp[i - 1][1] - prices[i](这里是和上一题唯一不一样的区别因为上道题最开始手里的钱是0元所以是0 - prices[i]只不过把0给省略了而这道题可以多次买卖股票如果是当天买进股票的话那么所得现金就是昨天不持有股票的所得现金 - 今天的股票价格)
2前一天买进股票dp[i - 1][0]
所以dp[i][0] max(dp[i - 1][0], -prices[i])
第i天不持有股票dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0])
代码实现动规
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(len, vectorint(2, 0));dp[0][0] - prices[0];dp[0][1] 0;for (int i 1; i len; i) {dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]);}return dp[len - 1][1];}
};
代码实现贪心
class Solution {
public:int maxProfit(vectorint prices) {int result 0;for(int i 1;i prices.size();i) {result max(prices[i] - prices[i - 1],0);}return result;}
};
