目錄

動態規劃怎么學？

1. 題目解析

2. 算法原理

1. 狀態表示

2. 狀態轉移方程

3. 初始化

4. 填表順序

5. 返回值

3. 代碼編寫

寫在最后：

---

動態規劃怎么學？

學習一個算法沒有捷徑，更何況是學習動態規劃，

跟我一起刷動態規劃算法題，一起學會動態規劃！

1. 題目解析

題目鏈接：978. 最長湍流子數組 - 力扣（LeetCode）

題目說要找出最長的湍流子數組，但是他的題干太長了，而且不止所云，

所以我們直接通過用例來分析什么是湍流子數組，

通過示例一我們知道了，湍流子數組就是一個大一小一個大一個小的子數組，

通過示例二我們知道了，如果數組一直是遞增/遞減，最長就是 2，

通過示例三我們知道了，如果數組只有一個元素，那么長度就是 1。

2. 算法原理

1. 狀態表示

我們還是從 dp [ i ] 來分析，

dp [ i ] 表示以 i 位置為結尾的所有子數組中，最長的湍流子數組的長度。

實際上他一共存在兩種情況：

f [ i ] 表示?i 位置為結尾的所有子數組中，上升狀態時最長的湍流子數組的長度，

g?[ i ] 表示?i 位置為結尾的所有子數組中，下降狀態時最長的湍流子數組的長度，

2. 狀態轉移方程

f [ i ] 分為三種情況：

當 f [ i - 1 ] >?f [ i ] ，要想進入上升狀態就得重新計算，所以變成 1?

當 f [ i - 1 ] <?f [ i ] ，下降狀態的最長長度就是 g [ i - 1 ] + 1

當 f [ i - 1 ] ==?f [ i ] ，要想進入平緩狀態就得重新計算，所以變成 1

g [ i ] 也同樣是這三種情況：

當 g?[ i - 1 ] > g?[ i ] ，上升狀態的最長長度就是 f?[ i - 1 ] + 1

當 g?[ i - 1 ] < g?[ i ] ，要想進入下降狀態就得重新計算，所以變成 1?

當 g?[ i - 1 ] == g?[ i ] ，要想進入平緩狀態就得重新計算，所以變成 1

3. 初始化

我們可以把所有位置先初始化成 1 作為初始值

4. 填表順序

從左往右，兩個表一起填。

5. 返回值

返回兩個表里面的最大值。

3. 代碼編寫

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();vector<int> f(n, 1), g(n, 1);int ans = 1;for(int i = 1; i < n; i++) {if(arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1;else if(arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1;ans = max(ans, max(f[i], g[i]));}return ans;}
};

寫在最后：

以上就是本篇文章的內容了，感謝你的閱讀。

如果感到有所收獲的話可以給博主點一個贊哦。

如果文章內容有遺漏或者錯誤的地方歡迎私信博主或者在評論區指出~