問題來源：leetcode 978。

最長湍流子數組

當 A 的子數組 A[i], A[i+1], ..., A[j] 滿足下列條件時，我們稱其為湍流子數組：

• 若 i <= k < j，當 k 為奇數時，A[k] > A[k+1]，且當 k 為偶數時，A[k] < A[k+1]；
• 或 若 i <= k < j，當 k 為偶數時，A[k] > A[k+1]，且當 k 為奇數時，A[k] < A[k+1]。
  也就是說，如果比較符號在子數組中的每個相鄰元素對之間翻轉，則該子數組是湍流子數組。

返回 A 的最大湍流子數組的長度。

示例 1：

輸入：[9,4,2,10,7,8,8,1,9] 輸出：5 解釋：(A[1] > A[2] < A[3] > A[4] < A[5])

示例 2：

輸入：[4,8,12,16] 輸出：2

示例 3：

輸入：[100] 輸出：1

提示：

• 1 <= A.length <= 40000
• 0 <= A[i] <= 10^9

動態規劃

優化子結構：設以 $arr[i]$ 為結尾的最長湍流子數組的長度為 $n$，證明該問題的最優解包含其子問題的最優解，或者說該問題的最優解可以由其子問題的最優解構造得到：

• 如果 $arr[i]==arr[i?1]$，那么以 $arr[i]$ 為結尾的最長湍流子數組的長度為 $1$，不需要子問題的解。
• 如果 $arr[i]>arr[i?1]$ 且 $arr[i?1]<arr[i?2]$，那么 $n?1$ 是子問題（以 $arr[i?1]$ 為結尾的數組）的最長湍流子數組的長度，也就是說只需要求解該子問題。可以通過反證法證明：假設子問題的最長湍流子數組的長度大于 $n?1$，那么又因為 $arr[i]>arr[i?1]$ 且 $arr[i?1]<arr[i?2]$，所以 $arr[i]$ 可以接在該湍流子數組的后面，所以以 $arr[i]$ 為結尾的最長湍流子數組的長度就大于 $n$，與假設矛盾。
• 如果 $arr[i]<arr[i?1]$ 且 $arr[i?1]>arr[i?2]$，那么 $n?1$ 是子問題（以 $arr[i?1]$ 為結尾的數組）的最長湍流子數組的長度，證明過程與前面相同。
• 對于其他情況（$arr[i]>arr[i?1]>arr[i?2]$ 或 $arr[i]<arr[i?1]<arr[i?2]$），那么無論以 $arr[i?1]$ 為結尾的最長湍流子數組的長度為多少，以 $arr[i]$ 結尾的最長湍流子數組的長度為 2。
• 還有 $arr[i?2]$ 不存在的情況，只需要看 $arr[i]$ 與 $arr[i]$ 是否相等，就可以得到原問題的解。

重疊子問題：簡單地使用遞歸算法來求解，很容易發現具有子問題被重復計算。

遞歸地定義最優解的值：設 $dp[i]$ 表示以 $arr[i]$ 結尾的最長湍流子數組的長度，對于數組的每個位置 $i$，以該位置元素結尾的最長湍流子數組的長度計算過程如下：

• 首先初始化 $dp$ 數組的所有位置都為 $1$。
• 如果 $dp[i?1]$ 為 1：
  • 如果 $arr[i]=arr[i?1]$ 時，$dp[i]=2$；
  • 否則保持 $1$ 不變。
• 否則：
  • 如果 $arr[i]>arr[i?1]$ 且 $arr[i?1]<arr[i?2]$ 或 $arr[i]<arr[i?1]$ 且 $arr[i?1]>arr[i?2]$，那么 $dp[i]=dp[i?1]+1$；
  • 否則看 $arr[i?1]$ 與 $arr[i]$ 是否相等，不相等的話將 $dp[i]$ 的值置為 $2$。

自底向上地計算最優解的值：只需要從前向后遍歷數組，便可以確保每一個問題計算時，其相關的子問題均已經被計算了出來。

class Solution { public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();if(n == 1) {return 1;}vector<int> dp(n, 1);for(int i = 1; i<n; i++) {if(dp[i-1] == 1) {dp[i] = arr[i-1] == arr[i] ? 1 : 2;} else if(arr[i] != arr[i-1]) {if((arr[i] > arr[i-1] && arr[i-1] < arr[i-2]) || (arr[i] < arr[i-1] && arr[i-1] > arr[i-2])) {dp[i] = dp[i-1] + 1;} else {dp[i] = 2;}}}return *max_element(dp.begin(), dp.end());} };

空間優化：注意到每個 $dp[i]$ 只與 $dp[i?1]$ 相關，所以可以通過一個變量來表示 $dp$ 數組，另外再通過一個變量保存當前最長湍流子數組的長度即可。

class Solution { public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();if(n == 1) {return 1;}int result = 1, temp = 1;for(int i = 1; i<n; i++) {if(temp == 1) {temp = arr[i-1] == arr[i] ? 1 : 2;} else if(arr[i] != arr[i-1]) {if((arr[i] > arr[i-1] && arr[i-1] < arr[i-2]) || (arr[i] < arr[i-1] && arr[i-1] > arr[i-2])) {temp++;} else {temp = 2;}}result = temp > result ? temp : result;}return result;} };

總結

以上是生活随笔為你收集整理的动态规划——最长湍流子数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。