b****g
发帖数: 192 | 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).
想不明白 ：（ |
l*****a
发帖数: 14598 | 2 那里有人贴答案了
two
【在 b****g 的大作中提到】
: 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).
: 想不明白 ：（
|
p*****p
发帖数: 379 | 3 From I you get the max profit through at most one transaction.
Then based on I's result you can use dp to get the max profit through at
most two.
two
【在 b****g 的大作中提到】
: 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).
: 想不明白 ：（
|
b****g
发帖数: 192 | 4 谁能给我讲讲题目是什么意思？
【在 l*****a 的大作中提到】
: 那里有人贴答案了
:
: two
|
c********w
发帖数: 2438 | 5 就是你最多能做两个transaction
但这两个transaction
第一个transaction的sell date必须早于或者等于第二个transaction的buy date
然后求最大的收益
【在 b****g 的大作中提到】
: 谁能给我讲讲题目是什么意思？
|
b****g
发帖数: 192 | 6 谢谢！
貌似做法和下面的题思路差不多。
左扫一遍，右扫一遍，这就属于DP了，然后就行了。
Multiplication of numbers
【在 c********w 的大作中提到】
: 就是你最多能做两个transaction
: 但这两个transaction
: 第一个transaction的sell date必须早于或者等于第二个transaction的buy date
: 然后求最大的收益
|
s********s
发帖数: 49 | 7 从头到尾扫一遍得到0..i的max profit
反向再扫一遍得到i..N的max profit
第三遍扫得到最大的sum,基本山是第一种best time to buy stocks的变形。下面这个
链接也有解释，可以参考。
http://tech-wonderland.net/blog/best-time-to-buy-and-sell-stock |
