这种方法抽象之后则为首先将 [1,n] 拆分为 [1,i] 和 [i+1,n], 参考卖股票系列的第一题计算各自区间内的最大利润即可。[1,i] 区间的最大利润很好算,但是如何计算 [i+1,n] 区间的最大利润值呢?难道需要重复 n 次才能得到?注意到区间的右侧 n 是个不变值,我们从 [1, i] 计算最大利润是更新波谷的值,那么我们可否逆序计算最大利润呢?这时候就需要更新记录波峰的值了。逆向思维大法好!Talk is cheap, show me the code!
classSolution: """ @param prices: Given an integer array @return: Maximum profit """ defmaxProfit(self, prices): if prices isNoneorlen(prices) <= 1: return0
n = len(prices) # get profit in the front of prices profit_front = [0] * n valley = prices[0] for i in xrange(1, n): profit_front[i] = max(profit_front[i - 1], prices[i] - valley) valley = min(valley, prices[i]) # get profit in the back of prices, (i, n) profit_back = [0] * n peak = prices[-1] for i in xrange(n - 2, -1, -1): profit_back[i] = max(profit_back[i + 1], peak - prices[i]) peak = max(peak, prices[i]) # add the profit front and back profit = 0 for i in xrange(n): profit = max(profit, profit_front[i] + profit_back[i])
classSolution { public: /** * @param prices: Given an integer array * @return: Maximum profit */ intmaxProfit(vector<int> &prices){ if (prices.size() <= 1) return0;
int n = prices.size(); // get profit in the front of prices vector<int> profit_front = vector<int>(n, 0); for (int i = 1, valley = prices[0]; i < n; ++i) { profit_front[i] = max(profit_front[i - 1], prices[i] - valley); valley = min(valley, prices[i]); } // get profit in the back of prices, (i, n) vector<int> profit_back = vector<int>(n, 0); for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) { profit_back[i] = max(profit_back[i + 1], peak - prices[i]); peak = max(peak, prices[i]); } // add the profit front and back int profit = 0; for (int i = 0; i < n; ++i) { profit = max(profit, profit_front[i] + profit_back[i]); }
classSolution { /** * @param prices: Given an integer array * @return: Maximum profit */ publicintmaxProfit(int[] prices) { if (prices == null || prices.length <= 1) return0;
// get profit in the front of prices int[] profitFront = newint[prices.length]; profitFront[0] = 0; for (inti=1, valley = prices[0]; i < prices.length; i++) { profitFront[i] = Math.max(profitFront[i - 1], prices[i] - valley); valley = Math.min(valley, prices[i]); } // get profit in the back of prices, (i, n) int[] profitBack = newint[prices.length]; profitBack[prices.length - 1] = 0; for (inti= prices.length - 2, peak = prices[prices.length - 1]; i >= 0; i--) { profitBack[i] = Math.max(profitBack[i + 1], peak - prices[i]); peak = Math.max(peak, prices[i]); } // add the profit front and back intprofit=0; for (inti=0; i < prices.length; i++) { profit = Math.max(profit, profitFront[i] + profitBack[i]); }