有趣的一題，一開始是以為用區間dp，dpij表示從i到j的最大值，結果發現有bug，然后通過最后求解想發到方法。 final = max(final, left[i] + right[i]); 其實我們只需要求出從左右兩邊算起來的最大值，不用把區間中的每一個小區間的最大值都求出來，所有就用了第一題的方法，從左邊算一次，再從右邊算一次（右邊算的優點不一樣，需要維護最大的數然后就sum，左邊是維護最小的數再維護最大的sum）
class Solution {public: int maxPRofit(vector<int>& prices) { if(prices.size() == 0) return 0; int n = prices.size(); int sum = 0, minn = prices[0]; vector<int>left(n, 0); vector<int>right(n, 0); for(int i = 1; i < n; ++ i){ if(prices[i] < minn) minn = prices[i]; else{ if(prices[i] - minn > sum) sum = prices[i] - minn; } left[i] = sum; } sum = 0; int maxx = prices[n - 1]; for(int i = n - 2; i >= 0; -- i){ if(prices[i] > maxx) maxx = prices[i]; else{ if(maxx - prices[i] > sum) sum = maxx - prices[i]; } right[i] = sum; } int final = 0; for(int i = 0; i < n - 1; ++ i){ final = max(final, left[i] + right[i]); } return final; }};新聞熱點
疑難解答
