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

一.题目解析算法解析:1.状态表示:dp[i]表示:以i位置为结尾的所有的子数组中,湍流子数组最长.我们发现一个状态不能概括完全的时候就需要增加状态表示,在距离i位置最近的一次状态中,前面的可能是增,也可能是减,或者是水平状态,所以我们增加上升和下降的状态.f[i]表示:以i位置为结尾的所有的子数组中,最后呈现上升状态的时候湍流子数组最长.g[i]表示:以i位置为结尾的所有的子数组中,最后呈现下降状态的时候湍流子数组最长.2.状态转移方程:3.初始化我们结合状态表示和状态转移方程就可以知道,单独的一个数可以构成一个可以看作是增或减或相等的一个子数组,所以初始表中全部位置都初始化为14.填表顺序从左向右填表5.返回值返回f表或g表的最大值二.代码编写:class Solution { public: int maxTurbulenceSize(vectorint arr) { int narr.size(); vectorintf(n,1);//全部初始化为1 auto gf; int ret1;//最小的长度都是1 for(int i1;in;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表 retmax(max(g[i],f[i]),ret);//返回值 } return ret; } };