第一題, 找到最佳進場點, 跟最佳出場點
easy 就不說明了
class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.size() == 0 || prices.size() == 1) {
return 0;
}
int history_small_value = prices.at(0);
int res = 0;
for (auto &price : prices) {
res = max(res, price - history_small_value);
history_small_value = min(history_small_value, price);
}
return res;
}
};第二題也放easy, 一開始我沒注意到條件沒有改, 我就一直在想這不可能是easy吧
原來是變成一天可以無限進出, 題目還是要多加看清楚, 可以進出的話我們就單純比較今天跟明天就好了, 會問說, 若我明天賣了, 後面變更高怎麼辦, 沒事，明天再買回來就好了, 因為一天可以一買一賣, 掃過一輪就能知道了, 若一天只能買or賣一次, 這題應該就要直接躍升hard了
class Solution {
public:
int maxProfit(vector<int> &prices) {
int res = 0;
for (int i = 0; i < prices.size() - 1; i++) {
if (prices[i] < prices[i + 1]) {
res += prices[i + 1] - prices[i];
}
}
return res;
}
};第三題直接進階成魔王, 題目變成是, 全部只能交易兩次(買兩次跟賣兩次), 且買了就一定要賣才能再買
我們先建立一個dp 的表, 這表紀錄兩個東西, 一個是交易的次數, 一個是當前i天最大收益, dp[k][i], 當k = 0, 一定都是0(因為壓根兒沒交易), 怎樣找到當dp[2][max_day]的值(題目是只能交易兩次)
我們就可以歸納出
dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j]), j=[0..i]等於是前一天的狀況, 跟今天賣的狀況去做比較, 後來發現當天也要加進去, 為什麼呢?
因為我有可能有一種狀況, 是當天賣掉, 當天又買下, 例如
[1, 2, 3, 4, 5]答案分別是買入賣出1,3,5
但可以注意到 3 的那天會賣出, 又買入
prices[i] - prices[j] + dp[k-1, j]今天的賣價(prices[i]) 買價(prices[j]),
這個到底是幹嘛的 dp[k-1, j]
原因是, 你可能在之前已經做過交易了, 我們得把那些交易一起找進來看才有意義
class Solution {
public:
int maxProfit(vector<int> &prices) {vector<vector<int>> dp(3, vector<int>(prices.size(), 0));
for (int k = 1; k <= 2; k++) {
for (int i = 1; i < prices.size(); i++) {
int max_value = 0;
for(int j = 0; j <= i; j++){
max_value = max(max_value, prices[i] - prices[j] + dp[k - 1][j]);
}dp[k][i] = max(dp[k][i-1], max_value);
}
}
return dp[2][prices.size() - 1];
};
};
但這種算法, 在數字大會TLE, 時間複雜度為O(kn²),我們有沒有辦法去精簡一下?
網路上有很多dp的精簡方法, 但我資質駑鈍, 我真的沒有很懂, 但還是要解決, 我們轉看其他方法
有個方法很神
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
if (prices.size() < 2)
{
return 0;
}
int buy1 = INT_MAX;
int sell1 = INT_MIN;
int buy2 = INT_MAX;
int sell2 = INT_MIN;
for (int i = 0; i < prices.size(); i++)
{
buy1 = min(buy1, prices[i]);
sell1 = max(sell1, prices[i] - buy1);
buy2 = min(buy2, prices[i] - sell1);
sell2 = max(sell2, prices[i] - buy2);
}
return sell2;
}
};buy1跟sell1的操作理念跟stock1很像, 我們就不再贅述
問題在 buy2 = min(buy2, prices[i] — sell1)
為什麼 要減去第一次的獲利?
我們今天假想一個狀況, 假設你已經在股市中, 賺了一百塊, 今天有一個３００塊的股票, 你會怎麼想? 我花三百塊買? 通常不會這樣想, 通常的想法是, 反正我已經賺了100塊, 相當於我這張股票我只用兩百塊買, 這就是buy2的做法
所以他先減去上次的獲利, 並且尋求最佳值
