1. 题⽬链接：978.最⻓湍流⼦数组
2. 题⽬描述：
3. 解法（动态规划）：
算法思路：
1. 状态表⽰：
我们先尝试定义状态表⽰为： dp[i] 表⽰「以i 位置为结尾的最⻓湍流数组的⻓度」。 但是，问题来了，如果状态表⽰这样定义的话，以i 位置为结尾的最⻓湍流数组的⻓度我们没法 从之前的状态推导出来。
因为我们不知道前⼀个最⻓湍流数组的结尾处是递增的，还是递减的。因 此，我们需要状态表⽰能表⽰多⼀点的信息：要能让我们知道这⼀个最⻓湍流数组的结尾是「递 增」的还是「递减」的。 因此需要两个dp 表：
f[i] 表⽰：以i 位置元素为结尾的所有⼦数组中，最后呈现「上升状态」下的最⻓湍流数 组的⻓度；
g[i] 表⽰：以i 位置元素为结尾的所有⼦数组中，最后呈现「下降状态」下的最⻓湍流数 组的⻓度。
2. 状态转移⽅程：
对于i位置的元素arr[i] ，有下⾯两种情况：
i. arr[i] > arr[i - 1] ：如果i 位置的元素⽐i - 1 位置的元素⼤，说明接下来 应该去找i -1 位置结尾，并且i - 1 位置元素⽐前⼀个元素⼩的序列，那就是g[i - 1] 。更新f[i] 位置的值： f[i] = g[i - 1] + 1 ；
ii. arr[i] < arr[i - 1] ：如果i 位置的元素⽐i - 1 位置的元素⼩，说明接下来 应该去找i - 1 位置结尾，并且i - 1 位置元素⽐前⼀个元素⼤的序列，那就是 f[i - 1] 。更新g[i] 位置的值： g[i] = f[i - 1] + 1 ；
iii. arr[i] == arr[i - 1] ：不构成湍流数组。
3. 初始化：
所有的元素「单独」都能构成⼀个湍流数组，因此可以将dp 表内所有元素初始化为1 。 由于⽤到前⾯的状态，因此我们循环的时候从第⼆个位置开始即可。
4. 填表顺序：
毫⽆疑问是「从左往右，两个表⼀起填」。
5. 返回值：
应该返回「两个dp 表⾥⾯的最⼤值」，我们可以在填表的时候，顺便更新⼀个最⼤值。
C++算法代码：
class Solution
{
public:
int maxTurbulenceSize(vector<int>& arr)
{
int n=arr.size();
//建表
vector<int>f(n,1); //以i位置为结尾最后趋向为上升的湍流数组长度
vector<int>g(n,1); //以i位置为结尾最后趋向为下降的湍流数组长度
//填表
int max_num=1;
for(int i=1;i<n;i++)
{
int a=arr[i-1],b=arr[i];
if(a>b)
{
f[i]=g[i-1]+1;
}
else if(a<b)
{
g[i]=f[i-1]+1;
}
max_num=max(max_num,max(f[i],g[i]));
}
//返回值
return max_num;
}
};Java算法代码：
class Solution
{
public int maxTurbulenceSize(int[] arr)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = arr.length;
int[] f = new int[n];
int[] g = new int[n];
for (int i = 0; i < n; i++) f[i] = g[i] = 1;
int ret = 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;
ret = Math.max(ret, Math.max(f[i], g[i]));
}
return ret;
}
}