【leetcode】Best Time to Buy and Sell Stock
【leetcode】Best Time to Buy and Sell Stock
阳光岛主
发布于 2019-02-19 11:28:51
发布于 2019-02-19 11:28:51
Question ：
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
for example： array[] = { 2, 5, 3, 8, 9, 4 } ， maxProfit = 9 - 2 = 7.
Anwser 1 ：
class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(prices.size() == 0) return 0;
int ret = 0;
int len = prices.size();
int maxPrice = prices[len-1];
for(int i = len - 1; i >= 0; i--){
maxPrice = max(prices[i], maxPrice); // maxPrice
ret = max(ret, maxPrice - prices[i]); // maxProfit
}
return ret;
}
};注意点：
最大利润，应该是先买的最低价与后卖的最高价的差值，因此需要考虑时间先后顺序
Anwser 2 ：
class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int maxp = 0;
int dp = 0;
for(int i = prices.size()-2; i >= 0 ;i--)
{
if(dp >= 0){
dp += (prices[i+1] - prices[i]);
} else {
dp = max(0, prices[i+1] - prices[i]);
}
maxp = max(dp, maxp);
}
return maxp;
}
};说明：
1） 此法把两数之间最大差，转化为了求两数组之间最大和
2） dp += (prices[i+1] - prices[i]) 实际上是 dp += (prices[i+1] - prices[i]) + (prices[i] - prices[i-1]) + (prices[i-1] - prices[i-2]) + ... = (prices[i] - prices[j]) （i > j）
参考推荐：
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013年04月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读