動態規劃之線性DP

?

（一）LIS問題

最長上升子序列

（樸素動規）

1.狀態的定義

要求出上升子序列中的最長長度，所以條件的限制只有必須要在序列中選這一個條件，所以只需要一維空間即可，

dp[i]表示以第i個字母結尾的子序列的最長子序列的長度，

2.遞推公式

如果在0~i中nums[j]比nums[i]大，那么nums[i]就可以接在nums[j]的后面成為上升子序列，所以有i-1個狀態可以退出dp[i]，所以遞推公式為dp[i] = max(dp[i], dp[j] + 1)

3.初始化

由遞推公式可知，單獨的一個字母就可以成為一個上升的子序列，所以dp[]陣列全部都要初始化為1，

4.遍歷順序

由遞推公式可知，前面的狀態退出后面的狀態，所以需要從前往后遍歷

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

• 時間復雜度 O(N²)

（二分+貪心+動規）

這里可以利用貪心的思想，將時間復雜度進一步的降低，

貪心的思想是：我們需要維護一個單調遞增的陣列，如果當前這個數比陣列末尾的數要大，那么說明這個陣列中的數需要往后延伸，加長上升子序列的長度，如果當前這個數比陣列末尾要小，那么就在這個有序陣列中找到第一個大于等于這個數的數，然后替換掉它，

第一種情況：就是num > dp.back()也就是在陣列沒有找到大于等于num的數，那么就在dp.back()后面添加當前數，這樣可以繼續保持上升，這種情況就是比較好理解，

第二種情況：這種情況比較不好理解，這里使用了貪心的思想，如果當前數比dp陣列中的數小，并且因為陣列是從前往后遍歷的，所以當前數的位置一定在已經在dp陣列中的數位置要靠后，所以此時就可以找到陣列中>=num的第一個數替換掉它，這樣下次就以當前這個數為有序陣列的結尾，這樣就可以使得數字更多的放進上升子序列中，

舉例：

dp = [2, 3, 5, 8，9], num[i] = 4, num[i + 1] = 6

此時為了后面可以得到更長的上升子序列，所以應該讓4替代5的位置，這樣dp=[2, 3, 4, 8]此時有序陣列的尾是4， 而不是8，這樣當nums[i+1]插入有序陣列的時候，就可以替換掉8的位置形成上升子序列，這樣替換可以使得后面可以接上更多的數字

注意：ans = fmax(ans, it - dp.begin() + 1)必須放在二分之后的，因為這里使用的是lower_bound()函式，所以回傳的迭代器會比較復雜，如果對迭代器經過修改之后再使用，那么可以會導致迭代器出現錯誤，

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp;
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
            ans = fmax(ans, it - dp.begin() + 1);
            if (it == dp.end()) dp.push_back(nums[i]);
            else *it = nums[i];
        }
        return ans;
    }
};

• 時間復雜度 O(Nlog_N)

最大子序和

（動規）

1.狀態定義

同樣還是只能在一個序列中求出子序列的和，所以只有一個限制，所以可以使用一維陣列來保存即可，

dp[i]表示以第i數結尾的連續子陣列的和的最大值為dp[i]，

2.遞推公式

因為是求出連續的子陣列的和，所以考慮狀態轉移的時候只需要考慮前面一個狀態即可，即dp[i - 1] + nums[i]和nums[i]比較，取一個最大值即可，

3.初始化

每一個數字都是一個連續的子陣列，所以以i結尾的連續子陣列的和至少為nums[i]，這個可以在回圈的時候賦值在dp[i]上即可，

4.遍歷順序

由遞推公式可知，一個狀態只由前一個狀態決定，所以從前往后遍歷即可，

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

（貪心）

我們可以貪心的發現，如果前面一個連續子陣列的和sum > 0，那么對于第i個數結尾的連續子陣列來說，可以使得這個子陣列的和增大，所以sum += nums[i]，否則，如果前面的子陣列的和<0，那么以i結尾的數字如果自己為一個子陣列的話，可以獲得更大的子陣列和，這時選擇nums[i]，

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN, sum = 0;
        for (int i = 0; i < nums.size(); i ++) {
            if (sum > 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
            ans = max(ans, sum);
        }
        return ans;
    }
};

最長連續遞增序列

（動規）

本題就是最長上升子序列的一個退化版本，即當前的狀態只有前面一個狀態轉移過來，所以只有當nums[i] > nums[i - 1]的時候，以i結尾的連續子陣列的長度才+1，其余的情況，只有nums[i]這一個數字充當連續的子陣列，長度為1，第一題和第二題如果理解的話，本題應該就沒有太大的問題了，這里就不詳細講了，

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

（雙指標）

也可以利用經典的雙指標演算法，將連續的子陣列摳出來，然后計算出子陣列的長度即可，最后比較所有的連續子陣列的長度，

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

俄羅斯套娃信封問題

只有一個信封的h和w都比另一個信封大的時候，才可以將信封套住，其實我們就是要尋找可以套住當前信封的信封，所以就要找一系列連續的大信封，這樣就可以才可以一環套一環，

**每一次合法的嵌套都是大的套小的信封，所以就相當于找一個最長上升子序列，其長度就是信封可以嵌套的信封數量，**所以這道題目本質上是一個最長上升子序列問題，

（二維LIS問題動規）

如果將二維的陣列看做一個整體，然后求出最長上升的子序列，那么就可以直接利用envelopes[i]0和envelopes[i][1]進行比較即可，

但是首先需要將陣列進行一個排序，因為只有當信封的大小是升序排序的時候，選擇出的最長上升子序列才是有意義的，

至于DP分析的程序，除了遞推公式判斷的時候需要判斷envelopes[i]0和envelopes[i][1]這兩個條件之外，其余的分析的程序都是一樣的，

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        vector<int> dp(n, 0);
        sort(envelopes.begin(), envelopes.end());
        int ans = 1;
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (envelopes[i][0] > envelopes[j][0] && 
                    envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（一維LIS問題）

如果覺得二維分析的時候有一些麻煩，其實也是可以常見的思維方式，即減少變數，

我們可以將h和w其中的一個先固定下來，比如說是w，可以對w進行升序排序；然后就可以直接對陣列中的第二維進行最長上升子序列的dp分析程序即可，

但是注意有一些特殊情況的時候，就不能滿足，當多個陣列中的第一維是相等的時候，如(1, 2), (1, 3), (1, 4)這時候其實因為信封的h并沒有嚴格的大于，所以是沒有信封可以嵌套的，但是如果只是用陣列中的第二維進行排序的話，最長上升子序列的長度卻是3個，這時其實就出現了沖突，

為了避免這種情況的出現，當陣列中第一維數字相同的時候，我們就不應該將有相同的第一維的數字算在最上升子序列中**，解決的方式是：可以在排序的是對第一維升序排序，但是如果第一維相同的情況下，進行降序排序，**這樣在計算第二維的時候，就可以避免沖突了，

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        vector<int> dp(n, 0);
        // 對第一維升序，在相同的情況下第二維降序
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>&b){
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] > b[1];
        });
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（一維LIS問題+二分貪心優化）

其實固定了第一維之后在進行一維的LIS問題，時間復雜度并沒有降低，但是二維LIS變成一維的LIS，最大的好處是：一維的上升子序列可以使用二分+貪心的優化（前面的題目中說過）這就可以使得時間復雜度變成O(log_N)了，但是二維的上升子序列在比較大小的時候不是很方便，所以就不采取二分的優化了，

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a,vector<int>& b){
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] > b[1];
        });
        int ans = 0;
        vector<int> dp;
        for (int i = 0; i < n; i ++) {
            auto it = lower_bound(dp.begin(), dp.end(), envelopes[i][1]);
            ans = fmax(ans, it - dp.begin() + 1);
            if (it == dp.end()) dp.push_back(envelopes[i][1]);
            else *it = envelopes[i][1];
        }
        return ans;
    }
};

堆箱子

（三維LIS問題動規）

剛剛上面的題目是二維的LIS問題，本題就是三維的LIS問題，

其實還有比較兩個陣列的大小問題，只不過是又多了一維而已，我們只需要在if判斷的時候，多加一個條件即可，

但是有兩個注意點：

1.本題不可以降維使用二分優化，因為三維空間就算使用排序固定一維，但是二維還是不可以二分的優化，

2.本題和普通的LIS問題不同的是，本題不是直接求出最長上升子序列的長度，而是在滿足最長上升子序列的條件下，計算累加的高度，所以遞推公式不再是dp[i] = max(dp[i], dp[j] + 1)，而是如果滿足上升的性質的時候，需要累加箱子的高度，

即dp[i]表示為以第i個箱子為底的箱子，上面累加的最高的高度為dp[i]，所以遞推公式是在轉移i的狀態高度上累加第j個箱子上應該放上box[i][2]，即遞推公式為dp[i] = max(dp[i], dp[j] + box[i][2])

class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        int n = box.size();
        int ans = 0;
        sort(box.begin(), box.end(), greater<vector<int>>());
        vector<int> dp(n);
        for (int i = 0; i < n; i ++) {
            dp[i] = box[i][2];
            for (int j = 0; j < i; j ++) {
                if (box[i][0] < box[j][0] && box[i][1] < box[j][1] 
                    					  && box[i][2] < box[j][2]){
                    dp[i] = max(dp[i], dp[j] + box[i][2]);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;      
    }
};

無重疊區間

（動規）

本題直接求出取出的最小區間數其實不太好算，但是如果算出無重復的區間數，就使得區間之間有了單調性，

但題目轉化為了求出無重復區間的數量的時候，就可以利用類似最長上升子序列的動規方法剞劂本題，

1.狀態定義

dp[i]表示以i結尾的區間，前面的區間中最多有dp[i]個無重復的區間數，

2.遞推公式

現在處于第i個區間，那么此時如果想要讓第i個區間在無重復的區間中，就必須列舉前i個區間中是否存在intervals[j][1]小于intervals[i][0]，這樣的話就可以使得第i個區間放在第j個區間中，所以遞推公式為dp[i] = max(dp[i], dp[j] + 1)，

這個遞推公式其實和LIS問題的遞推公式是一樣的，其實兩個題目的思想都是一樣的，可以說本題其實就是求出最長不重復區間的序列數量，兩道題目都是在序列中找，當滿足某一個性質的時候（可能是必須滿足遞增的序列或者是滿足不重復區間的序列）狀態可以轉移，

3.初始化

每一個區間都至少是一個不重復的區間，所以可以將dp陣列都初始化為1

注意：由于區間是二維的，所以不能使用二分的優化，所以O(N²)的效率是很低的，

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        vector<int> dp(n, 0);
        int max_elem = 0;  // 無重復區間的最大數量
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (intervals[i][0] >= intervals[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_elem = max(max_elem, dp[i]);
        }
        return n - max_elem;
    }
};

本題也可以利用貪心的思想，我們可以貪心地想：當排完序之后，要得到最小的重復區間數，也就是得到最多的無重復區間數，那么每一次兩個區間如果重疊的話，我們取區間右邊界小的一個區間作為下一次判斷的右邊界，

因為如果右邊界大的話，下一次要滿足無重復區間的左邊界就會變大，這樣滿足條件的區間就會變少，所以我們貪心地選取右邊界小的區間，

實作這樣貪心的方式有兩種：第一種就是求出移除的區間數，第二種就是求出無重復區間的最大數量，然后最后用intervals.size()減一下即可，

（貪心1）

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end());
        int ans = 0;
        int r = intervals[0][1];
        int n = intervals.size();
        for (int i = 1; i < n; i ++) {
            if (intervals[i][0] < r) {
                ans ++;
                r = min(r, intervals[i][1]);
            } else {
                r = intervals[i][1];
            }
        }
        return ans;
    }
};

（貪心2）

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        int max_cnt = 1; // 無重復區間的最大數量
        int l = intervals[0][0], r = intervals[0][1];
        for (int i = 1; i < n; i ++) {
            if (intervals[i][0] >= r) {
                max_cnt ++;
                l = intervals[i][0];
                r = intervals[i][1];
            } else {
                r = min(r, intervals[i][1]);
            }
        }
        return n - max_cnt;
    }
};

用最少數量的箭引爆氣球

本題是上一題的練習，但是需要將戳氣球問題轉換成為求無重復區間的數量，將一個氣球的直徑看成是一段區間，要用最少的弓箭數將所有的區間有覆寫到，那么其實重復區間可以使用一個弓箭即可，這就是利用貪心的思想，那么要使得弓箭覆寫到所喲的區間，就可以求出所有的無重復區間的數量，這樣和無重復區間重疊的區間也就都被覆寫到了，

所以本題就轉化為了求出區間的無重復區間數量，可以使用上題說的動規和貪心，但是由于動規會超時這里就不寫了，

（貪心）

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();
        sort(points.begin(), points.end());
        int l = points[0][0], r = points[0][1];
        int ans = 1;
        for (int i = 1; i < n; i ++) {
            if (points[i][0] > r) {
                ans ++;
                l = points[i][0];
                r = points[i][1];
            } else {
                r = min(r, points[i][1]);
            }
        }
        return ans;
    }
};

最長數對鏈

在一個線性的序列中，陣列對之間滿足某一種性質之后，可以進行線性的遞推，所以本題還是可以使用LIS問題的思想來解決的，

當滿足pair[i][0]大于pair[j][1]的時候（j < i），這就滿足了數對鏈的條件，所以就可以將pair[i][0]放入數對鏈中，其實和求出上升子序列沒有什么區別，只是我們將>的意義重新的定義了一遍而已，所以本題就是LIS問題，所以可以使用動規來解決，

（動規）

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end());
        int ans = 0;
        vector<int> dp(n, 0);
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（貪心）

**如果換一個角度，可以將數對中的兩個數，看成一段區間中的兩個端點，這樣其實就可以使用貪心的思想求出無重復的區間的數量問題，**這樣可以進一步的降低時間復雜度，

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end());
        int r = pairs[0][1];
        int ans = 1;
        for (int i = 1; i < n; i ++) {
            if (pairs[i][0] > r) {
                ans ++;
                r = pairs[i][1];
            } else {
                r = min(r, pairs[i][1]);
            }
        }
        return ans;
    }
};

（貪心右端點sort）

前面所有的類似求出無重復區間的問題，我們都是通過讓區間的左端點排序，可以固定區間的一端，然后我們只需要比較另一端即可，

但是每一次我們發現了重疊的區間之后，需要更新區間的右端點，這里我們為了貪心的得到覆寫所有區間的范圍，所以每一次盡量讓區間的右端點都盡量的小，這樣就可以留下更多的空間給剩下的區間，

其實可以在區間排序的時候，做一些手腳，就是我們既然知道每一次都要取右端點最小的區間，我們干脆直接將區間按右端點排序，如果是這樣的是，如果不滿足r < pairs[i][0]的情況下，就可以不用更新區間的右端點，因為已經將區間排好序了，所以從左向右區間的右端點就是從小到大的，

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end(), [](auto& a, auto& b){
            return a[1] < b[1];
        });
        int r = INT_MIN;
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            if (r < pairs[i][0]) {
                ans ++;
                r = pairs[i][1];
            }
        }
        return ans;
    }
};

最長字串鏈

本題作為LIS問題最后一彈，可以作為最終的檢驗，是否真正地理解了LIS問題，

由題目可知，本題需要首先排序，使得單詞的長度由小到大，這樣可以方便地找出單詞的前身，

然后的任務就是找到單詞之間是否存在前身關系，如果滿足單詞之間的前身關系，那么當前的單詞就是加入到前面一個單詞串列之中，

所以本題就是LIS問題+如果判斷一個字串中包含了另一個字串和任意一個字符，我們可以使用雙指標的方法就可以很容易地判斷是否有存在關系了，

（動規）

class Solution {
public:
    bool check(string& a, string& b) {
        bool flag = false;
        int pa = 0, pb = 0;
        while (pa < a.size()) {
            if (a[pa] != b[pb]) {
                if (flag) return false;
                pb ++;
                flag = true;
            } else {
                pa ++;
                pb ++;
            }
        }
        return true;
    }

    int longestStrChain(vector<string>& words) {
        int n = words.size();
        sort(words.begin(), words.end(),[](auto& a, auto& b){
            return a.size() < b.size();
        });

        vector<int> dp(n, 0);
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (words[i].size() == words[j].size() + 1 && 
                    check(words[j], words[i])) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（二）前后綴陣列

除自身以外陣列的乘積

看到所有求出除了當前位置上的數之外，所有的數的乘積，其實最開始的想法一定都是直接將所有數先都乘起來，然后每一次都用所有數的乘積除以當前位置上的數即可，

但是有兩個問題：1.當陣列中出現0的時候，就不能使用，2.題目中規定了不能出現除法，

（動規）

所以我們可以想一些更暴力的方法，即遇到一個數的時候，可以計算出當前位置左邊所有的數的乘積，然后計算出當前位置上右邊所有數的乘積，最后左右兩邊的數再做一次乘積即可，

但是這樣做的時間復雜度為O(N²)的，所以我們可以使用前后綴陣列做一個優化，即left[i]記錄0~i-1所有數的乘積，right[i]記錄i + 1 ~ n - 1所有數的乘積，因為已經將每一個位置上左右兩邊的乘積都預處理了，所以最后只需要O(N)的時間復雜度就可以求出答案了，這就是典型的前后綴陣列的空間換時間，

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n), right(n);
        left[0] = 1;
        for (int i = 1; i < n; i ++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i --) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        vector<int> ans;
        for (int i = 0; i < n; i ++) {
            ans.push_back(left[i] * right[i]);
        }
        return ans;
    }
};

（動規空間優化）

其實我們還可以在上面的基礎上，去掉前后綴陣列，就是使用vector<int> ans答案陣列，充當前后綴陣列的作用，

我們可以使用一個變數充當連續數字的乘積，即首先使用答案陣列預處理出來左邊的前綴乘積，然后再反向的在答案陣列中再處理后綴乘積的時候，使用一個變數記錄從后往前的乘積tmp，所以在回圈到第i個位置的時候，tmp表示后i個數的乘積，此時dp[i] *= tmp就是左右兩邊的陣列乘積相乘了，

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = 1;
        for (int i = 1; i < n; i ++) {
            dp[i] = dp[i - 1] * nums[i - 1];
        }
        int tmp = 1; // 記錄第i個位置右邊所有數的乘積
        for (int i = n - 2; i >= 0; i --) {
            tmp *= nums[i + 1];
            dp[i] *= tmp;
        }
        return dp;
    }
};

陣列中的最長山脈

（動規列舉山頂）

一個山峰是由上坡和下坡組成的，所以直接暴力列舉每一個位置的左右兩邊的連續遞增或者遞減的陣列即可，這就和前面一題處理前后綴乘積一樣，需要先預處理一下前后綴和連續遞增或者遞減的陣列，這樣可以增加計算的效率，

如果arr[i] > arr[i - 1]那么prxfix[i] = prefix[i - 1] + 1，否則的話，pre[i]就等于1，同樣的，后綴陣列suffix的預處理也是一樣，

最后ans = max(prefix[i] + suffix[i] - 1)即可，但是有一點需要注意，題目中需要的陣列必須是有上坡和下坡的，所以當prefix[i]或者suffix[i]有一個是1的話，那么就不能構成山峰，所以就不能更新ans，

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        // 預處理前后綴陣列
        vector<int> prefix(n, 1);
        for (int i = 1; i < n; i ++) {
            if (arr[i] > arr[i - 1]) {
                prefix[i] = prefix[i - 1] + 1;
            }
        }
        vector<int> suffix(n, 1);
        for (int i = n - 2; i >= 0; i --) {
            if (arr[i] > arr[i + 1]) {
                suffix[i] = suffix[i + 1] + 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i ++) {
            // 如果prefix或者suffix中有一個是1的話說明不能形成山峰
            if (prefix[i] > 1 && suffix[i] > 1) 
                ans = max(ans, prefix[i] + suffix[i] - 1);
        }
        return ans >= 3 ? ans : 0;
    }
};

（列舉山腳）

因為本題中的山峰陣列是連續的山峰，所以可以列舉山腳，然后順著山腳列舉到山峰，最后在從山峰下到山腳，這樣列舉山腳的方式就是在勾勒出整個山峰，

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        int i = 1;
        int ans = 0;
        while (i < n) {
            int up = 0, down = 0;
            while (i < n && arr[i] > arr[i - 1]) i ++, up ++;
            while (i < n && arr[i] < arr[i - 1]) i ++, down ++;
            if (up > 0 && down > 0)
                ans = max(ans, up + down + 1);
            while (i < n && arr[i] == arr[i - 1]) i ++;
        }
        return ans >= 3 ? ans : 0;
    }
};

接雨水

（動規-前后綴陣列）

如果想要形成雨水的話，就要形成低洼的地方，所以最暴力的方法就是列舉每一個位置左右兩邊的最大的柱子的高度，（注意：是左右兩邊的最大高度，不是離得最近的兩個高度，因為要一次性地算出一個位置上能接的所有雨水，一定是從全域的角度看，而不是只看最近的高度，）

這種暴力的方法，我們知道可以使用前后綴陣列來優化，所以使用兩個陣列r[i], l[i]表示第i個位置上的左右兩邊的最大高度，最后的答案就是ans += h - min(l[i], r[i])，

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> l(n), r(n);
        for (int i = 1; i < n; i ++) {
            l[i] = max(l[i - 1], height[i - 1]);
        }
        for (int i = n - 2; i >= 0; i --) {
            r[i] = max(r[i + 1], height[i + 1]);
        }
        int ans = 0;
        for (int i = 1; i < n - 1; i ++) {
            int h = min(l[i], r[i]);
            if (h > height[i]) {
                ans += h - height[i];
            }
        }
        return ans;
    }
};

（雙指標）

根據木桶原理，水量是由最短的木板決定的，所以我們就可以關注短木板一段的水量即可，

為了一次性找出一個位置上的所有蓄水量，所以我們使用兩個指標指向兩個木板，并且兩個指標是分別指向兩端的，

然后我們需要兩個變數lMax和rMax來記錄左邊和右邊的最大高度，如果不足最大的高度，那么椴木板就可以形成低洼，如果當前的木板比對應邊的最大高度要高，那就不能形成低洼處，我們就要更新對應邊的木板最大高度，

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int lMax = 0, rMax = 0;
        int l = 0, r = n - 1;
        int ans = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (lMax > height[l]) {
                    ans += lMax - height[l];
                } else {
                    lMax = height[l];
                }
                l ++;
            } else {
                if (rMax > height[r]) {
                    ans += rMax - height[r];
                } else {
                    rMax = height[r];
                }
                r --;
            }
        }
        return ans;
    }
};

（三）經典問題

*環形子陣列的最大和

（最小/最小子陣列和）

在一個陣列求出最大的子陣列的和起前面已經解決了，本題的區別在于頭尾部的子陣列可以跨越中間的陣列，然后求出最大子陣列的和，

所以我們這里就多加了一種情況，第一種就是最大的子陣列和在原陣列的中間部分，第二種是最大子陣列和在原陣列有原陣列的頭尾兩端構成，

第一種情況就是最大子陣列和那一道題，

第二種情況看起來就不太好求了，但是我們可以換一個思路，如果頭尾陣列和最大，那么我們只需要使得sum - 中間部分的陣列和，那么就是要讓中間部分的陣列和最小，這不就轉化為了求出整個陣列的最小子陣列和么，

所以我們就可以在遞推的時候，將陣列中的最大最小子陣列和都求出來，最后的答案就是max(maxVal, sum - minVal)，但是要注意的是，如果整個陣列都是負數，那么sum - minVal就是0了，而maxVal一定是一個負數，所以這個時候應該去maxVal而不是sum-minVal（也就是0），所以我們需要特判，如果maxVal < 0那么說明整個陣列都是負數，這時直接回傳maxVal即可，

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        int sum = nums[0]; // 陣列中所有數的和
        vector<int> minDp(n), maxDp(n);
        int minVal = nums[0], maxVal = nums[0];// 最大/最小子陣列和
        minDp[0] = nums[0], maxDp[0] = nums[0];// 初始化dp陣列

        for (int i = 1; i < n; i ++) {
            sum += nums[i];
            minDp[i] = min(nums[i], nums[i] + minDp[i - 1]);
            minVal = min(minVal, minDp[i]);
            maxDp[i] = max(nums[i], nums[i] + maxDp[i - 1]);
            maxVal = max(maxVal, maxDp[i]);
        }

        if (maxVal < 0) return maxVal; // 如果陣列中的數都為負數,則回傳maxVal
        return max(maxVal, sum - minVal);
    }
};

（動規 + 空間優化）

因為最大/最小子陣列和的遞推公式是dp[i - 1]轉移到dp[i]的，所以可以使用兩個變數來做空間優化，

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        int sum = nums[0]; // 陣列中所有數的和
        int minDp = nums[0], maxDp = nums[0];
        int minVal = nums[0], maxVal = nums[0];// 最大/最小子陣列和

        for (int i = 1; i < n; i ++) {
            sum += nums[i];
            minDp = min(nums[i], nums[i] + minDp);
            minVal = min(minVal, minDp);
            maxDp = max(nums[i], nums[i] + maxDp);
            maxVal = max(maxVal, maxDp);
        }

        if (maxVal < 0) return maxVal; // 如果陣列中的數都為負數,則回傳maxVal
        return max(maxVal, sum - minVal);
    }
};

（單調佇列+前綴和）

當解決「環形的陣列」的問題的時候，我們通常的辦法都是「破環成鏈」，即環形陣列就是兩個相同的陣列組合而成，那么我們可以將兩個相同的陣列拉成一條鏈狀結構，

當環形的陣列變成了線性的陣列的時候，我們就是可以使用遞推的方式來求解子陣列的和了，

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        vector<int> sum(2 * n + 1);
        // 處理前綴和
        for (int i = 1; i <= 2 * n; i ++) {
            sum[i] = sum[i - 1] + nums[(i - 1) % n];
        }

        deque<int> q;
        // 虛擬節點
        q.push_back(0); 
        int ans = INT_MIN;
        for (int i = 1; i <= 2 * n; i ++) {
            // 維護視窗中元素的有效性
            if (!q.empty() && i - n > q.front()) q.pop_front(); 
            // 更新答案
            ans = max(ans, sum[i] - sum[q.front()]);  
            // 保持視窗中元素的單調性
            while (!q.empty() && sum[q.back()] >= sum[i]) q.pop_back();
            q.push_back(i);
        }
        return ans;
    }
};

*乘積最大子陣列

（暴力）

最暴力的方法就是將所有的子序列都列舉一遍，因為最終要求得最大的子陣列一定是連續的，所以可以使用n²的時間復雜度就會算出來了，

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

（動規）

本題乍一眼看起來其實是很像「最大子陣列和」那一道題目的，但是仔細一想，對于乘法來說，可能當前位置是一個負數，但是由于下一個數也是負數，這時候反而希望負數越小越好，這樣最終的乘積才會更大，所以根據這一點，所以我們需要同時保存一個乘積過后的最大值和一個乘積過后的最小值，

1.狀態定義

maxDp[i]表示以第i個位置為結尾的最大陣列乘積，minDp[i]表示以第i個位置結尾的最小陣列乘積，

2.遞推公式

根據nums[i]的正負號，我們可以分出兩種情況：

1.如果nums[i] >= 0的話，maxDp[i] = maxDp[i - 1] * nums[i]，minDp[i] = minDp[i - 1] * nums[i]，最后maxDp[i]和minDp[i]要和nums[i]本身再比較一下，得出遞推公式nums[i] = max(maxDp[i - 1] * nums[i], nums[i])，nums[i] = min(minDp[i - 1] * nums[i], nums[i])，

2.同樣的，如果nums[i] < 0，maxDp[i] = max(nums[i] * minDp[i - 1], nums[i]);，minDp[i] = min(nums[i] * maxDp[i - 1], nums[i]);，

3.初始化

根據遞推公式，我們需要從1開始遍歷，所以需要初始化minDp[0] = nums[0]和maxDp[0] = nums[0]，

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> minDp(n), maxDp(n);
        minDp[0] = nums[0]; maxDp[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; i ++) {
            if (nums[i] > 0) {
                maxDp[i] = max(nums[i] * maxDp[i - 1], nums[i]);
                minDp[i] = min(nums[i] * minDp[i - 1], nums[i]);
            } else {
                maxDp[i] = max(nums[i] * minDp[i - 1], nums[i]);
                minDp[i] = min(nums[i] * maxDp[i - 1], nums[i]);
            }
            ans = max(ans, maxDp[i]);
        }
        return ans;
    }
};

（動規+空間優化）

我們發現dp陣列在遞推的程序中，每一個狀態只由前一個狀態遞推出來，所以可以使用滾動陣列的形式回圈地使用陣列，這樣就可以省去O(N)的空間，

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int minDp = nums[0], maxDp = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; i ++) {
            if (nums[i] > 0) {
                maxDp = max(nums[i] * maxDp, nums[i]);
                minDp = min(nums[i] * minDp, nums[i]);
            } else {
                int tmp = maxDp;
                maxDp = max(nums[i] * minDp, nums[i]);
                minDp = min(nums[i] * tmp, nums[i]);
            }
            ans = max(ans, maxDp);
        }
        return ans;
    }
};

（動規空間優化的簡潔寫法）

其實每一次狀態轉移只有三種情況，所以我們可以不用分出nums[i]到底是大于0還是小于0，可以直接將三種狀態直接轉移即可，

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int ans = nums[0];
        int minVal = nums[0], maxVal = nums[0];
        for (int i = 1; i < n; i ++) {
            int ta = maxVal, ti = minVal;
            maxVal = max(max(nums[i], ta * nums[i]), ti * nums[i]);
            minVal = min(min(nums[i], ti * nums[i]), ta * nums[i]);
            ans = max(ans, maxVal);
        }
        return ans;
    }
};

矩陣的最大非負積

（動規）

和上一道題目類似，因為是乘積的最值，所以會出現負數乘以負數反而變大的情況，因此我們需要同時記錄當前路徑下可以達到的最大值和最小值，

1.狀態定義

minDp[i][j]表示從(0,0)到(i,j)路徑上的最小乘積，maxDp[i][j]表示從(0,0)到(i,j)路徑上的最小乘積，

2.遞推公式

對于nums[i]的正負，分成兩種情況，

如果nums[i] >= 0，正數乘以大數=大數，正數乘以小數=小數，所以maxDp[i][j] = max(maxDp[i - 1][j], maxDp[i][j - 1]) * grid[i][j];,minDp[i][j] = min(minDp[i - 1][j], minDp[i][j - 1]) * grid[i][j];，

如果nums[i] < 0，負數乘以大數=小數，負數乘以小數=大數，所以maxDp[i][j] = min(minDp[i - 1][j], minDp[i][j - 1]) * grid[i][j];，minDp[i][j] = max(maxDp[i - 1][j], maxDp[i][j - 1]) * grid[i][j];，

3.初始化

根據遞推公式，第一行和第一列的路徑上的最大最小值只有一個方向可以遞推，所以需要手動的初始化，

要注意的是：和上一道題目不同的是本題求的是路徑上的最值乘積，和子陣列中的連續最值乘積是不同的，這里的狀態轉移只能是從上或者從左轉移過來的，而自己本身不是一個狀態，所以就不能從中間的路徑斷開，

在上一題中因為連續的子陣列乘積所以自己本身也是一個狀態，所以可以從陣列中的中間提取出子陣列的乘積作為答案，所以即使是線性的遞推，但是還是可以每一個位置都有不同的最大最小值，

class Solution {
public:
    const int mod = 1e9 + 7;
    using LL = long long;
    int maxProductPath(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<LL>> maxDp(n, vector<LL>(m));
        vector<vector<LL>> minDp(n, vector<LL>(m));
        minDp[0][0] = maxDp[0][0] = grid[0][0];
        for (int i = 1; i < n; i ++) {
            minDp[i][0] = maxDp[i][0] = maxDp[i - 1][0] * grid[i][0];
        }
        for (int i = 1; i < m; i ++) {
            minDp[0][i] = maxDp[0][i] = maxDp[0][i - 1] * grid[0][i];
        }
        for (int i = 1; i < n; i ++) {
            for (int j = 1; j < m; j ++) {
                if (grid[i][j] >= 0) {
                    maxDp[i][j] = max(maxDp[i - 1][j], maxDp[i][j - 1]) * grid[i][j];
                    minDp[i][j] = min(minDp[i - 1][j], minDp[i][j - 1]) * grid[i][j];
                } else {
                    maxDp[i][j] = min(minDp[i - 1][j], minDp[i][j - 1]) * grid[i][j];
                    minDp[i][j] = max(maxDp[i - 1][j], maxDp[i][j - 1]) * grid[i][j];
                }
            }
        }
        return maxDp[n - 1][m - 1] < 0 ? -1 : maxDp[n - 1][m - 1] % mod;
    }
};

擺動序列

（動規）

本題很像「最長上升子序列」，但是有一個很不一樣的地方就是：最長上升子序列不具有連續的傳遞性，而最長擺動序列有，比方說：1,3,5,2,9，如果求出擺動序列的長度的話，當考慮9的時候，我們需要考慮9的前面是5的情況，而是直接考慮9的前面是2的情況即可，因為2的前面是5，所以在2這個地方的轉折一定會被算進2所在的擺動序列當中，所以在計算以9結尾的數字的時候，可以直接考慮2和9的大小情況即可，、

所以在遞推公式判斷的時候，我們只需要判斷nums[i]和nums[i - 1]的情況即可，遞推擺動序列的長度，

1.狀態定義

up[i]表示以i結尾并且在i這個點上升的擺動序列的長度，down[i]表示以i結尾并且在i這個位置下降的擺動序列的長度，

2.遞推公式

如果nums[i] > nums[i - 1]，那么說明序列在上升，所以up[i] = max(up[i - 1], down[i - 1] + 1)，

如果nums[i] < nums[i - 1]，那么說明序列在下降，所以down[i] = max(down[i - 1], up[i - 1] + 1)，

3.初始化

因為每一個位置都可以成為一個序列，所以dp可以全部初始化為1，

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> up(n, 1), down(n, 1);
        int ans = 1;
        for (int i = 1; i < n; i ++) {
            if (nums[i] > nums[i - 1]) {
                up[i] = max(up[i - 1], down[i - 1] + 1);
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {
                down[i] = max(down[i - 1], up[i - 1] + 1);
                up[i] = up[i - 1];
            } else {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
            ans = max({ans, up[i], down[i]});
        }
        return ans;
    }
};

（動規空間優化）

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        int up = 1, down = 1;
        for (int i = 1; i < n; i ++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return max(up, down);
    }
};

（貪心）

每一個點都是一個數字，我們可以貪心地想要使得擺序列的長度更大，所以需要將擺動序列的峰值上下落差大，因為這樣落在擺動的程序中的點才可以更多，

如果我們不取最大值為擺動序列的極值點，那么擺動序列中的可能出現的峰值就會越小，這樣出現擺動的機會就會越小，所以要取最大/最小值當做擺動序列的峰值，

注意：前后相同的數字是不能構成擺動序列的，所以我們需要先對陣列中的數字去重，

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        int n = nums.size();
        if (n <= 2) return n;
        int ans = 2;// 默認頭尾節點一定在擺動序列當中
        for (int i = 1; i < n - 1; i ++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ans ++;
            if (nums[i] < nums[i - 1] && nums[i] < nums[i + 1]) ans ++;
        }
        return ans;
    }
};