【leetcode】BestTimetoBuyandSellStock
Question :
Say you have an array for which the
i
th
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 19:39:15
侵权处理: 本个人博客,不盈利,若侵犯了您的作品权,请联系博主删除,莫恶意,索钱财,感谢!