首页 > 代码库 > [leetcode-123-Best Time to Buy and Sell Stock III]
[leetcode-123-Best Time to Buy and Sell Stock III]
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
开始的时候思路很朴素:以为与leetcode-121-Best Time to Buy and Sell Stock差不多
就是选取一个分割点j,在j左边与右边分别进行计算最大值,然后统计最大值之和。时间复杂度为O(n2).没有通过
最后一个数据量特别大的测试用例。
int maxProfitcore(vector<int>& prices,int start,int end) {//从start 到 end期间 最大profit if (start == end|| prices.size()==0) return 0; int tempProfit = 0, maxProfit = 0; for (int i = start+1; i <=end; i++) { tempProfit += prices[i] - prices[i - 1]; tempProfit = max(0, tempProfit); maxProfit = max(maxProfit, tempProfit); } return maxProfit; }//超时 int maxProfit3(vector<int>& prices) { int profit = 0; for (int i = 1; i < prices.size();i++) { int pro1 = maxProfitcore(prices, 0, i); int pro2 = maxProfitcore(prices, i, prices.size()-1); profit = max(profit,pro1+pro2); } return profit; }
后来参考大神代码:
只需扫描一趟就行,复杂度为O(n).
如下:
int maxProfitnew(vector<int>& prices) { int size = prices.size(); if (size == 0 || size == 1) return 0; vector<int>profit(size,0); vector<int>profit1(size); int local_min = prices[0]; int local_max = prices[size - 1]; int j = size - 2; int result = 0; profit[0] = 0; profit1[size - 1] = 0; for (int i = 1; i < size + 1 && j >= 0; i++, j--)//扫描一遍,分别计算左边和右边最大的profit { //记录i左边最大profit 利用i-1的信息 只需比较i-1时候的profit 与现在price-local_min即可 //如果prices[i] - local_min >profit[i - 1]的话,说明需要更新最大的profit 同理 求右边最大profit也是一个道理 profit[i] = max(profit[i - 1], prices[i] - local_min); local_min = min(local_min, prices[i]); profit1[j] = max(profit1[j + 1], local_max - prices[j]);//记录j右边最大profit local_max = max(local_max, prices[j]); } for (int i = 1; i < size; i++)//统计左右两边最大profit之和 取最大 { result = max(result, profit[i] + profit1[i]); } return result; }
参考:
https://discuss.leetcode.com/topic/15177/simple-dp-8ms-solution-for-best-time-to-buy-and-sell-stock-iii
http://blog.csdn.net/fightforyourdream/article/details/14503469
[leetcode-123-Best Time to Buy and Sell Stock III]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。