这道题实际上就是最大差值问题。之一更新最小值或最大值，以及当前最大差值即可。
这道题由于是两次购入，所有分别从左右两端求得然后相加即可。
class Solution {public: int maxProfit(vector<int>& prices) { int res = 0; const int size = prices.size(); if(size == 0) return res; vector<int> vec(size, 0); //从左往右计算vec[i]（vec1[i]）表示，第1..i+1天的最大收益，因为数组下标从零开始 int min = prices[0]; for(int i=1; i<size; ++i){ vec[i] = vec[i-1]; //如果收益没有之前的多，至少要保持 if(prices[i] - min > vec[i]) //以当天为界限，计算之前的最大收益，所以是减 vec[i] = prices[i] - min; if(prices[i] < min) min = prices[i]; } //从右往左计算vec2[i]表示，第i+1天到最后一天的最大收益 //这里由于采用vec2[i]空间复杂度为O(2n),所以利用profit变量省去vec2[i]，直接在vec[i]上相加即可 int max = prices[size-1], profit = 0; for(int i=size-2; i>=0; --i){ if(max - prices[i] > profit) //以当天为界，未来的最大收益，则是更远的天数减去更近的天数 profit = max - prices[i]; vec[i] += profit; //在这里直接+=,直接将之前算的某天以前的最大收益和目前某天以后最大收益相加，节省空间复杂度 if(prices[i] > max) max = prices[i]; } for(int i=0; i<size; ++i) //找出某一天满足最大收益最大 res = std::max(res, vec[i]); return res; }};新闻热点
疑难解答
