這道題實際上就是最大差值問題。之一更新最小值或最大值，以及當前最大差值即可。
這道題由于是兩次購入，所有分別從左右兩端求得然后相加即可。
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; }};新聞熱點
疑難解答
