a***e
发帖数: 413 | 1 别人的答案，但不太清楚怎么能证明或者保证两个区间没有相交？我开始是想照CC150
上说的那样把所有可能的情况列出来找规律，但到后面越想就越糊涂了。多谢！
比如
1235
12305
10325
1032502
‘You may not engage in multiple transactions at the same time (ie, you must
sell the stock before you buy again).’
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).
// LeetCode, Best Time to Buy and Sell Stock III
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
int maxProfit(vector& prices) {
if (prices.size() < 2) return 0;
const int n = prices.size();
vector f(n, 0);
vector g(n, 0);
for (int i = 1, valley = prices[0]; i < n; ++i) {
valley = min(valley, prices[i]);
f[i] = max(f[i - 1], prices[i] - valley);
}
for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) {
peak = max(peak, prices[i]);
g[i] = max(g[i], peak - prices[i]);
}
int max_profit = 0;
for (int i = 0; i < n; ++i)
max_profit = max(max_profit, f[i] + g[i]);
return max_profit;
}
}; | d********t
发帖数: 9628 | 2 绿皮书原题，kadanes algo
CC150
must
【在 a***e 的大作中提到】
: 别人的答案，但不太清楚怎么能证明或者保证两个区间没有相交？我开始是想照CC150
: 上说的那样把所有可能的情况列出来找规律，但到后面越想就越糊涂了。多谢！
: 比如
: 1235
: 12305
: 10325
: 1032502
: ‘You may not engage in multiple transactions at the same time (ie, you must
: sell the stock before you buy again).’
: Say you have an array for which the ith element is the price of a given
| a***e
发帖数: 413 | | g****9
发帖数: 163 | 4 我是这样子想的 要是有交集的话 那只需要交易一次就可以了，题目说的是最多可以交
易两次。比如 你用DP的算法算出来 第一天买进 第五天卖出 第五天买入 第十天卖出
的时候profit最多 这样子的话 其实可以看做第一天买进 第十天卖出 只交易一次就行
了 不知道这样子回答你了没有
CC150
must
【在 a***e 的大作中提到】
: 别人的答案，但不太清楚怎么能证明或者保证两个区间没有相交？我开始是想照CC150
: 上说的那样把所有可能的情况列出来找规律，但到后面越想就越糊涂了。多谢！
: 比如
: 1235
: 12305
: 10325
: 1032502
: ‘You may not engage in multiple transactions at the same time (ie, you must
: sell the stock before you buy again).’
: Say you have an array for which the ith element is the price of a given
|
|
