首页 > 代码库 > Best Time to Buy and Sell Stock III <leetcode>
Best Time to Buy and Sell Stock III <leetcode>
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
思路:这个题本来行到的分成两部分,分别用动态规划,后来在由于做第一个题的时候,看到过一个比较简单的动态规划,因此在这里直接用了,(虽然代码写的不同,想法不同,但是我们用的都是动态规划),一下比较简洁的动态规划的代码:
1 class Solution { 2 public: 3 int maxProfit(vector<int> &prices) { 4 int minl=INT_MAX; 5 int maxr=INT_MIN; 6 7 int size=prices.size(); 8 if(size==0) return 0; 9 vector<int> f1(size);10 vector<int> f2(size);11 12 minl=prices[0];13 14 for(int i=1;i<size;i++)15 {16 minl=min(minl,prices[i]);17 f1[i]=max(f1[i-1],prices[i]-minl);18 }19 20 maxr=prices[size-1];21 22 for(int i=size-2;i>=0;i--)23 {24 maxr=max(maxr,prices[i]); 25 f2[i]=max(f2[i+1],maxr-prices[i]);26 }27 28 int sum = 0;29 for (int i = 0; i < size; i++)30 sum = std::max(sum, f1[i] + f2[i]);31 32 return sum;33 }34 };
Best Time to Buy and Sell Stock III <leetcode>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。