注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex123 Best Time to Buy and Sell Stock III  

2015-05-25 21:46:06|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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).


第一次做这个股价买卖的时候想复杂了,不过就是求最低股价和当前收益的问题,虽然也是动态规划,我以前用了最大子数组和的算法,完全是大材小用。这一题,原本没什么思路。这里有个性质就是,第一次交易完成必须在第二次买之前,所以可以确定一个时间点i,前面是第一次交易最大值,后面是第二次交易最大值。所以就可以分别维护两个数组dpLeft[i]  和dpRight[i]。
dpLeft[i]表示从开始到i的最大收益,dpRight[i]表示从i到最后的最大收益。这样最后扫描一下这两个数组,求和取最大值就可以了。见c++代码

/*
* 现在看来,我当时第一次做这个题的貌似还想复杂了
* 第一种根本用不着那个求最大数组和

* 这道题最朴素的思想就是在i这一点分界,左边交易最大和右边交易最大加起来
* 然后最后扫一遍就可以了
* 不过复杂度貌似会很高
* 如果用动态规划的话,两边都维护一个数组就可以了
*/
class Solution {
public:
int maxProfit(vector<int>& prices) {

int len = prices.size();
if (len <= 0)
return 0;
vector<int>dpLeft(len,0);
vector<int>dpRight(len,0);

int i, j;
int minPrice = prices[0];
dpLeft[0] = 0;
for (i = 1; i < len; i++)
{
minPrice = myMin(minPrice,prices[i]);
dpLeft[i] = myMax(dpLeft[i-1],prices[i]-minPrice);
}

dpRight[len - 1] = 0;
int maxPrice = prices[len-1]; //倒着推的时候就应该是最大price 减去当前prices了
for (i = len-2; i >=0; i--)
{
maxPrice = myMax(maxPrice, prices[i]);
dpRight[i] = myMax(dpRight[i+1], maxPrice-prices[i]);
}

int profit = 0;
for (i = 0; i<len; i++)
{
int tmp = dpLeft[i] + dpRight[i];
if (tmp > profit)
profit = tmp;
}

return profit;
}
int myMin(int a,int b)
{
return a > b ? b : a;
}
int myMax(int a, int b)
{
return a > b ? a : b;
}
};


后面还有一个更加变态的升级版,目前还没有什么想法。
  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017