有趣的一题，一开始是以为用区间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; }};新闻热点
疑难解答
