动态规划问题,建立两个数组,存储0-i的最大增益,i-end的最大增益,然后遍历i可得到结果。
参考:
https://www.cnblogs.com/theskulls/p/5430265.html
int Max(int a, int b) { return a > b ? a : b; } int maxProfit(vector<int>& prices) { if (prices.size() < 2) return 0; vector<int> lMax(prices.size(), 0); vector<int> rMax(prices.size()+1, 0); int min = prices[0]; for (int i = 1; i < prices.size(); i++) { if (prices[i] >= min) { lMax[i] = Max(lMax[i-1], prices[i] - min); } else { min = prices[i]; lMax[i] = lMax[i - 1]; } } int max = prices[prices.size()-1]; for (int i = prices.size() - 2; i > 0; i--) { if (prices[i] <= max) { rMax[i] = Max(rMax[i + 1], max - prices[i]); } else { max = prices[i]; rMax[i] = rMax[i+1]; } } int result = 0; for (int i = 0; i < prices.size(); i++) result = Max(result, lMax[i] + rMax[i+1]); return result; }