题目:
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
思路:
动态规划
dp[i]:截止第i天的最大利润
第i天可执行的操作:不做任何操作、买入股票、卖出股票
对应的dp[i]: dp[i-1]、-price[i]、price[i] - min_price
状态转移公式: dp[i] = max(dp[i-1], -price[i], price[i] - min_price)
= max(dp[i-1], price[i] - min_price)
该思路的实现见代码一。
观察该思路的状态转移公式,可知:后一个dp的值只依赖前一个dp的值,所有可以不使用dp数组,而是维护一个变量来记录dp的值,从而进一步优化空间使用,优化后的版本见代码二。
代码一:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
vector<int> dp(n, 0);
int min_price = prices[0];
dp[0] = 0;
for(int i=1; i<n; i++)
{
dp[i] = max(dp[i-1], prices[i] - min_price);
min_price = min(min_price, prices[i]);
}
return dp.back();
}
};
代码二:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int min_price = prices[0];
int dp = 0;
for(int i=1; i<n; i++)
{
dp = max(dp, prices[i] - min_price);
min_price = min(min_price, prices[i]);
}
return dp;
}
};
本文来源:http://tiandingtougu.com/64379.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件举报,一经查实,本站将立刻删除。