本文主要是介绍**Leetcode 123 Best Time to Buy and Sell Stock III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/
O(n^2)的做法就不解释了，枚举划分的位置即可。但是关键点在最多两次，所以可以考虑前缀后缀和。
先说O(n^2)的
class Solution {
public:int maxProfitForOne(vector<int>& prices, int l, int r) { if (r - l == 0) return 0; int ret = 0, cur_min = prices[l]; for (int i = l+1; i < r; i++) { ret = max(ret, prices[i] - cur_min); if (prices[i] < cur_min) { cur_min = min(prices[i], cur_min); } } return ret; } bool needJudge(vector<int>& prices, int idx) {idx -= 1;if (idx == 0 || idx == prices.size()-1) return true;if (prices[idx] >= prices[idx - 1] && prices[idx] > prices[idx + 1])return true;elsereturn false;}int maxProfit(vector<int>& prices) {if (prices.size() <= 1) return 0;int ret = 0, left = 0, right = 0;for (int sp = 1; sp < prices.size() + 1; sp ++) {if (!needJudge(prices, sp)) continue;left = maxProfitForOne( prices, 0, sp );right = maxProfitForOne( prices, sp, prices.size() );ret = max( ret, left + right );}return ret;}
};O(n)的 维护前缀后缀，注意边界。。。当时我想到的一个O(4*n)的分情况比较多
class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() <= 1) return 0;int prefix[prices.size()+1], suffix[prices.size()+1];prefix[0] = 0; suffix[prices.size()] = 0;int cur_min = prices[0], cur_ans = 0;for (int i = 1; i < prices.size(); i++) {cur_ans = max(cur_ans, prices[i] - cur_min);prefix[i] = cur_ans;if (prices[i] < cur_min) cur_min = prices[i];}int cur_max = prices[prices.size()-1];cur_ans = 0; for (int i = prices.size() - 1; i >= 0; i--) {cur_ans = max(cur_ans, cur_max - prices[i]);suffix[i] = cur_ans;if (prices[i] > cur_max) cur_max = prices[i];}int ret = 0;for (int i = 0; i < prices.size(); i++) {ret = max(ret, prefix[i] + suffix[i+1]);}return ret;}
};然后发现还有更好的解：空间O(1)时间O(n)
https://discuss.leetcode.com/topic/5934/is-it-best-solution-with-o-n-o-1
http://blog.csdn.net/u012501459/article/details/46514309
这篇关于**Leetcode 123 Best Time to Buy and Sell Stock III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
