leetcode-Best Time to Buy and Sell Stock III

一维DP。
 1 class Solution {
 2     //Best time to buy and sell stock III
 3     //correct one
 4 public:
 5     int maxProfit(vector<int> &prices) {
 6         if (prices.size() == 0 || prices.size() == 1) return 0;
 7         const int n = prices.size();
 8         vector<int> f(n,0);
 9         vector<int> g(n, 0);
10         int minV = prices[0];
11         int maxV = prices[n - 1];//一开始定义的max变量，跟算法里的max函数重名了。
12         for (int i = 1; i < n; i++)
13         {//f[i]是记录[0..i]中的最大收益，是从前向后算的
14             f[i] = max(f[i-1], prices[i] - minV);
15             if (minV>prices[i])
16                 minV = prices[i];
17         }
18         for (int i = n-2; i >=0; i--)
19         {//g[i]是记录[i..n-1]中的最大收益，是从后向前算的
20                 if (maxV < prices[i])
21                 maxV = prices[i];
22                 g[i] = max(g[i+1],maxV-prices[i]);
23         }
24         int maxRet=0;
25         for (int i = 0; i < n; i++)
26         {
27             maxRet =max( f[i] + g[i],maxRet);
28         }
29         return maxRet;
30     }
31 };