i****y
发帖数: 58 | 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******i
发帖数: 76 | 2 可不可以循环两次，每次都找到最大的max profit，
第一次循环结束后，删除这两个数，然后在循环找到另一对
不知道这样可行否 |
i****y
发帖数: 58 | 3 这样找出来的两对很有可能重叠，感觉是不是要用dp做了。。。
【在 d******i 的大作中提到】
: 可不可以循环两次，每次都找到最大的max profit，
: 第一次循环结束后，删除这两个数，然后在循环找到另一对
: 不知道这样可行否
|
s*****n
发帖数: 162 | 4 第一轮，从左到右算，到第i天截至，做一次交易的最大收益。
第二轮，从右到左算，从第j天开始到最后一天，做一次交易的最大收益。同时算做两
次交易的最大收益：加上第一轮已经知道的，到第j天截至，做一次交易的最大收益。O
(n) time |
c****9
发帖数: 164 | 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*******w
发帖数: 1243 | 6
。O
还是你牛！
【在 s*****n 的大作中提到】
: 第一轮，从左到右算，到第i天截至，做一次交易的最大收益。
: 第二轮，从右到左算，从第j天开始到最后一天，做一次交易的最大收益。同时算做两
: 次交易的最大收益：加上第一轮已经知道的，到第j天截至，做一次交易的最大收益。O
: (n) time
|
w****x
发帖数: 2483 | 7
。O
要死啦,刚准备想想怎么做就一不小心看到你把答案揭晓了.
【在 s*****n 的大作中提到】
: 第一轮，从左到右算，到第i天截至，做一次交易的最大收益。
: 第二轮，从右到左算，从第j天开始到最后一天，做一次交易的最大收益。同时算做两
: 次交易的最大收益：加上第一轮已经知道的，到第j天截至，做一次交易的最大收益。O
: (n) time
|
c********t
发帖数: 5706 | 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]: {
|
