网站免费大全,石家庄网站定制开发,山西时代网站建设,phyton 网站开发题目链接#xff1a;https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
给定一个数组#xff0c;它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易#xff08;多次买卖一支股票…题目链接https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1:
输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。 示例 2:
输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。 因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。 示例 3:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示
1 prices.length 3 * 10 ^ 4 0 prices[i] 10 ^ 4 解题报告
比较相邻两天如果价格跌了则处理掉手中的股票并买入当天的股票这一步是为了统一所有情况方便写代码反之则不卖股票。
AC代码贪心
class Solution {
public:int maxProfit(vectorint prices) {int keep_price prices[0];int ans 0;for(int i 1; iprices.size(); i) {if(prices[i] prices[i-1]) {ans prices[i-1] - keep_price;keep_price prices[i];}}ans prices[prices.size()-1]-keep_price;return ans;}
};
解题报告2
直接dp。
考虑到「不能同时参与多笔交易」因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。
定义状态dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润i从 0 开始。
注意因为定义的不是赚的钱而是交易结束后手里还有多少钱可以是负数那种。所以不需要管上次从哪开始买不然需要再来一层循环了直接用上一天的随时更新着点当前手里的钱就行了。
AC代码dp
class Solution {
public:int dp[30005][2];int maxProfit(vectorint prices) {dp[0][0] 0;dp[0][1] -prices[0];for(int i 1; iprices.size(); 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[prices.size() - 1][0];}
};
错误代码
class Solution {
public:int dp[30005][2];int maxProfit(vectorint prices) {dp[0][0] 0;dp[0][1] -prices[0];for(int i 1; iprices.size(); i) {dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i-1]);dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i]);}return dp[prices.size() - 1][0];}
};class Solution {
public:int dp[30005][2];int maxProfit(vectorint prices) {dp[0][0] 0;dp[0][1] -prices[0];for(int i 1; iprices.size(); i) {dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i-1]);dp[i][1] max(dp[i-1][1]-prices[i-1]prices[i], dp[i-1][0] - prices[i]);}return dp[prices.size() - 1][0];}
};
