本文主要是介绍「动态规划」如何求最长湍流子数组的长度？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
78. 最长湍流子数组
https://leetcode.cn/problems/longest-turbulent-subarray/description/
给定一个整数数组arr，返回arr的最长湍流子数组的长度。如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。更正式地来说，当arr的子数组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]。
- 输入：arr = [9,4,2,10,7,8,8,1,9]，输出：5，解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]。
- 输入：arr = [4,8,12,16]，输出：2。
- 输入：arr = [100]，输出：1。
提示：1 <= arr.length <= 4 * 10^4，0 <= arr[i] <= 10^9。
我们用动态规划的思想来解决这个问题。
确定状态表示：根据经验和题目要求，我们用dp[i]表示：以i位置为结尾的所有子数组中，最长湍流子数组的长度。但是这样的状态表示推不出状态转移方程，所以我们需要更细的划分：
- 用f[i]表示：以i位置为结尾的所有最后呈现上升趋势的子数组中，最长湍流子数组的长度。
- 用g[i]表示：以i位置为结尾的所有最后呈现下降趋势的子数组中，最长湍流子数组的长度。
推导状态转移方程：考虑最近的一步。以i位置为结尾的湍流子数组和以i - 1位置为结尾的湍流子数组有什么关系呢？以f[i]为例，分类讨论：
- 如果arr[i - 1] >= arr[i]，那么以i位置为结尾的最后呈现上升趋势的最长湍流子数组就是arr[i]本身，即f[i] = 1。
- 如果arr[i - 1] < arr[i]，那么以i位置为结尾的最后呈现上升趋势的最长湍流子数组，就应该是「以i - 1位置为结尾的最后呈现下降趋势的最长湍流子数组」的末尾添加arr[i]之后，形成的湍流子数组，即f[i] = g[i - 1] + 1。
综上所述：f[i] = arr[i - 1] >= arr[i] ? 1 : g[i - 1] + 1。同理，g[i] = arr[i - 1] <= arr[i] ? 1 : f[i - 1] + 1。换句话说，f[i]和g[i]默认是1，如果arr[i - 1] < arr[i]，那么f[i] = g[i - 1] + 1；如果arr[i - 1] > arr[i]，那么g[i] = f[i - 1] + 1。
初始化：根据状态转移方程，我们需要初始化f[0]和g[0]的值，防止越界。显然f[0] = g[0] = 1。
填表顺序：根据状态转移方程，显然应从左往右，同时填两个表。
返回值：根据状态表示，由于我们不确定最长湍流子数组的结束位置，所以应返回f表和g表中，所有元素的最大值。
细节问题：显然f表和g表的规模和arr相同，均为1 x n。
时间复杂度：O(N)，空间复杂度：O(N)。
class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n = arr.size();// 创建dp表vector<int> f(n, 1);auto g = f;// 填表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;}}// 返回结果return max(*max_element(f.begin(), f.end()),*max_element(g.begin(), g.end()));}
};这篇关于「动态规划」如何求最长湍流子数组的长度？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
