【leetcode】123. Best Time to Buy and Sell Stock III

时间:2021-02-07 23:54:37
@requires_authorization
@author johnsondu
@create_time 2015.7.22 19:04
@url [Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)
/************************
* @description: dynamic programming.
* 从前后分别求出当前所能够得到的最大值,最后相加而得
* 详细操作是,设置一个最小值,然后不断更新最小值。然后不断更新最大值。 前后反向累加求得最大值
* @time_complexity: O(n)
* @space_complexity: O(n)
************************/
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int len = prices.size();
if(len < 2) return 0;
int maxFromHead[len];
maxFromHead[0] = 0;
int minprice = prices[0], maxprofit = 0;
for(int i = 1; i < len; i ++) {
minprice = min(prices[i-1], minprice);
if(maxprofit < prices[i] - minprice)
maxprofit = prices[i] - minprice;
maxFromHead[i] = maxprofit;
}
int maxprice = prices[len-1];
int res = maxFromHead[len-1];
maxprofit = 0;
for(int i = len-2; i >= 0; i --) {
maxprice = max(maxprice, prices[i+1]);
if(maxprofit < maxprice - prices[i])
maxprofit = maxprice - prices[i];
if(res < maxFromHead[i] + maxprofit)
res = maxFromHead[i] + maxprofit;
}
return res;
}
};
@requires_authorization
@author johnsondu
@create_time 2015.7.22 19:04
@url [Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)
/************************
* @description: dynamic programming.
* 超时做法:从1開始。分成前后两段,最后求得前后两段的最大值
* @time_complexity: O(n^2)
* @space_complexity: O(n)
************************/
class Solution {
public:
int maxProfit(vector<int>& prices) {
int p_size = prices.size();
if(p_size < 2) return 0;
if(p_size < 3) {
return prices[1] - prices[0] > 0 ? prices[1] - prices[0]: 0;
} int ans = 0;
for(int i = 1; i < p_size; i ++) {
vector<int> dp1, dp2;
for(int j = 1; j <= i; j ++) {
dp1.push_back(prices[i] - prices[i-1]);
}
for(int j = i + 1; j < p_size; j ++) {
dp2.push_back(prices[j] - prices[j-1]);
} int dp1_size = dp1.size();
int ans1 = 0;
int cur = 0;
for(int j = 0; j < dp1_size; j ++) {
cur = cur + dp1[j];
if(cur < 0) {
cur = 0;
continue;
}
if(cur > ans1) ans1 = cur;
} int dp2_size = dp2.size();
int ans2 = 0;
cur = 0;
for(int j = 0; j < dp2_size; j ++) {
cur = cur + dp2[j];
if(cur < 0) {
cur = 0;
continue;
}
if(cur > ans2) ans2 = cur;
}
ans = max(ans, ans1 + ans2);
}
return ans;
}
};