首页 > 代码库 > Best Time to Buy and Sell Stock III <leetcode>

Best Time to Buy and Sell Stock III <leetcode>

2024-07-21 12:28:37   213人阅读

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>


联系
我们