1. 題意

有一個股價變化圖，你可以在一天買入，在未來一天賣出。

求通過這樣一次操作的最大獲利。

2. 題解

2.1 枚舉

直接枚舉，買入賣出的時間，肯定會超時啦~

時間復雜度為$O(n^2)$
空間復雜度為$O(1)$

class Solution {
public:int maxProfit(vector<int>& prices) {int ans = 0;int n = prices.size();for (int i = 0;i < n;++i) {for(int j = i + 1;j < n; ++j) {ans = max(ans, prices[j] - prices[i]);}}return ans;}
};

2.2 貪心

我們不難想到，我們每次賣股票的時候，只需要買入當前股票之前最低股份的股票就可以了！因此我們可以邊統計最低股價，一邊計算差值的最大值。

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int ans = 0;int mn = prices[0];for (int i = 1; i < n; ++i) {ans = max(prices[i] - mn, ans);mn  = min(mn, prices[i]);}return ans;}
};

2.3 動態規劃

動態規劃的思路和貪心的感覺差不多，也不知道這算不算動態規劃~

我們用$dp[i]$表示賣出的股票是$prices[i]$時的最大差值。

因此$ans=\max \left\{dp[i]|1\le i\le prices.size()?1\right\}$。

同樣對于$dp[i]$，我們需要知道$i$之前的最小股份，所以最終代碼跟

貪心差不多？空間優化完后，代碼估計就跟貪心一樣，就不寫了。

class Solution {
public:int maxProfit(vector<int>& prices) {int n   = prices.size();int ans = 0;vector<int> dp(n + 1, 0);int mn = prices[0];for (int i = 0;i < n; ++i) {dp[i + 1] = max( dp[i], prices[i] - mn);mn = min( prices[i], mn);}return dp[n];}
};

2.4 差分+動態規劃

這個題目跟lc53 最大子數組和, 是相互變形的關系。

其實也就是差分和前綴和的關系。

lc53可以通過前綴和轉換成這個問題，當然這個問題也可以通過差分變成

最大子數組和。貼個代碼吧，也懶得再解釋了OvO

class Solution {
public:int maxProfit(vector<int>& prices) {adjacent_difference( prices.begin(), prices.end(), prices.begin());prices[0] = 0;int ans = 0;int pre = 0;for (auto v: prices) {pre += v;ans = max( pre, ans);if (pre < 0)pre = 0;}return ans;}
};