动态规划_最长湍流子数组_C++

一.题目解析

算法解析:

1.状态表示:

dp[i]表示:以i位置为结尾的所有的子数组中,湍流子数组最长.

我们发现一个状态不能概括完全的时候就需要增加状态表示,在距离i位置最近的一次状态中,前面的可能是增,也可能是减,或者是水平状态,所以我们增加上升和下降的状态.

f[i]表示:以i位置为结尾的所有的子数组中,最后呈现"上升"状态的时候湍流子数组最长.

g[i]表示:以i位置为结尾的所有的子数组中,最后呈现"下降"状态的时候湍流子数组最长.

2.状态转移方程:

3.初始化

我们结合状态表示和状态转移方程就可以知道,单独的一个数可以构成一个可以看作是增或减或相等的一个子数组,所以初始表中全部位置都初始化为1

4.填表顺序

从左向右填表

5.返回值

返回f表或g表的最大值

二.代码编写:

class Solution { public: int maxTurbulenceSize(vector<int>& arr) { int n=arr.size(); vector<int>f(n,1);//全部初始化为1 auto g=f; int ret=1;//最小的长度都是1 for(int i=1;i<n;i++) { if(arr[i-1]<arr[i])f[i]=g[i-1]+1;//填f表 else if(arr[i-1]>arr[i])g[i]=f[i-1]+1;//填g表 ret=max(max(g[i],f[i]),ret);//返回值 } return ret; } };