最佳时机"/>
68 买卖股票的最佳时机
买卖股票的最佳时机
- 题解1 贪心
- 题解2 DP
给定一个数组
prices
,它的第
i
个元素
prices[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 <=
prices.length
<= 1 0 5 10^5 105 - 0 <=
prices[i]
<= 1 0 4 10^4 104
题解1 贪心
class Solution {
public:int maxProfit(vector<int>& prices) {const int s = prices.size();int inf = 1e9;int maxprofitvalue = 0;int minL = inf;int idx = 0;// 贪心就是顺着一个方向往前走,走一步看一步(但是要记录下前面的关键值)for(auto& i : prices){maxprofitvalue = max(maxprofitvalue, i-minL);// 记录 i对应位置前的最小值minL = min(i, minL);}return maxprofitvalue;}
};
题解2 DP
class Solution {
public:int maxProfit(vector<int>& prices) {const int s = prices.size();// dp[i] : 第i天不持有(0), or持有(1)vector<vector<int>> dp(s, vector<int>(2, 0));for(int i = 0; i < s; i++){if(! i){// base case// 不持有,收益=0dp[i][0] = 0;// 持有, 存在支出dp[i][1] = -prices[i];continue;}// 第i天不持有,两种情况:前一天不持有,i天也不持有; 前一天持有,i天卖出转为不持有dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);// 第i天持有,两种情况:前一天也持有,i天没卖; 前一天不持有,i天买的dp[i][1] = max(dp[i-1][1], -prices[i]);}// 最后返回的是不持有的情况(要卖出呀,不能砸手里)return dp[s-1][0];}
};
更多推荐
68 买卖股票的最佳时机
发布评论