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.
思路：
刚开始我想着先找出每个位置之前的min，和每个位置之后的max。然后用一个双循环来算最大可能profit，结果超时了。
接着想想干脆先找出每个位置之前（包括此位置）交易所有可能最大profit值，记录为 max_left[i].
在从后往前找出每个位置之后交易所有可能最大profit值，记录为 max_right[i].
接下来就简单了。一个for loop 解决问题。
java版本，384 ms过，回头贴上code
| Accepted | 384 ms |
没有评论:
发表评论