Best Time to Buy and Sell Stock 出三了。。。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Best Time to Buy and Sell Stock 出三了。。。

Best Time to Buy and Sell Stock 出三了。。。# JobHunting - 待字闺中

i*y2012-11-07 08:11

1 楼

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).
大家有没有思路啊。。。

d*i2012-11-07 08:11

2 楼

可不可以循环两次，每次都找到最大的max profit，
第一次循环结束后，删除这两个数，然后在循环找到另一对
不知道这样可行否

i*y2012-11-07 08:11

3 楼

这样找出来的两对很有可能重叠，感觉是不是要用dp做了。。。

【在 d******i 的大作中提到】

: 可不可以循环两次，每次都找到最大的max profit，
: 第一次循环结束后，删除这两个数，然后在循环找到另一对
: 不知道这样可行否

s*n2012-11-07 08:11

4 楼

第一轮，从左到右算，到第i天截至，做一次交易的最大收益。
第二轮，从右到左算，从第j天开始到最后一天，做一次交易的最大收益。同时算做两
次交易的最大收益：加上第一轮已经知道的，到第j天截至，做一次交易的最大收益。O
(n) time

c*92012-11-07 08:11

5 楼

这个牛逼，顺着思路写了下：
int maxProfit(vector &prices) {
vector left(prices.size(),0);
vector right = left;
int max= 0 ;
int min = INT_MAX;
for(int i=0;i{
if(prices[i]{
min = prices[i];
}
if(prices[i]-min>max)
{
max = prices[i]-min;
}
left[i]= max;
}
max = 0;
int rightmax = INT_MIN;
for(int i=prices.size()-1;i>=0;i--)
{
if(prices[i]>rightmax)
{
rightmax = prices[i];
}
if(rightmax-prices[i]>max)
{
max = rightmax-prices[i];
}
right[i] = max;
}
max =0;
for(int i=0;i{
if(left[i]+right[i]>max)
{
max = left[i]+right[i];
}
}
return max;
}

。O

【在 s*****n 的大作中提到】

: 第一轮，从左到右算，到第i天截至，做一次交易的最大收益。
: 第二轮，从右到左算，从第j天开始到最后一天，做一次交易的最大收益。同时算做两
: 次交易的最大收益：加上第一轮已经知道的，到第j天截至，做一次交易的最大收益。O
: (n) time

f*w2012-11-07 08:11

6 楼

。O
还是你牛！

【在 s*****n 的大作中提到】

w*x2012-11-07 08:11

7 楼

。O
要死啦,刚准备想想怎么做就一不小心看到你把答案揭晓了.

【在 s*****n 的大作中提到】

c*t2012-11-07 08:11

8 楼

可以试试再简化些。

【在 c****9 的大作中提到】

: 这个牛逼，顺着思路写了下：
: int maxProfit(vector &prices) {
: vector left(prices.size(),0);
: vector right = left;
: int max= 0 ;
: int min = INT_MAX;
: for(int i=0;i: {
: if(prices[i]: {