EEPW论坛

Say you have an array for which the i thelement is the price of a given stock on dayi.

Design an algorithm to find the maximum profit. You may complete at most twotransactions.

Note: 
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题意：股票最多能卖两次，求最大收益；

思路：动态规划，以第i天为分界线，计算第i天之前进行一次交易的最大收益pre[i]，和第i天之后进行一次交易最大收益postProfit[i]

最后遍历一遍max(pre[i]+post[i])最大值

1. class Solution  

2. {  

3.     int maxProfit(vector<int> &prices)  

4.     {  

5.         if (prices.size()<=1)  

6.         {  

7.             return 0;  

8.         }  

9.   

10.         int n = prices.size();  

11.         int * preProfit = new int[n]();  

12.         int * postProfit = new int[n]();  

13.   

14.         int curMin = prices[0];  

15.         for (int i=1; i<n; i++)  

16.         {  

17.             curMin = min(curMin, prices[i]);  

18.             preProfit[i] = max(preProfit[i-1], prices[i]-curMin);  

19.         }  

20.   

21.         int curMax = prices[n-1];  

22.         for (int i=n-2; i>=0; i--)  

23.         {  

24.             curMax = max(curMax, prices[i]);  

25.             postProfit[i] = max(postProfit[i + 1], curMax - prices[i]);  

26.         }  

27.   

28.         int maxProfit = 0;  

29.         for (int i = 0; i<n; i++)  

30.         {  

31.             maxProfit = max(maxProfit, postProfit[i] + preProfit[i]);  

32.         }  

33.         delete[] postProfit;  

34.         delete[] preProfit;  

35.         return maxProfit;  

36.     }  

37. };