买了房子后，给buyer broker and loan broker礼物卡么？# Living
a*e
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;
}
};
上说的那样把所有可能的情况列出来找规律，但到后面越想就越糊涂了。多谢！
比如
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
if (prices.size() < 2) return 0;
const int n = prices.size();
vector
vector
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;
}
};
