购物展示网站开发的背景,网站编辑信息怎么做,wordpress安装网站无法,吉林建筑信息平台目录
力扣978. 最长湍流子数组
解析代码 力扣978. 最长湍流子数组
978. 最长湍流子数组
难度 中等
给定一个整数数组 arr #xff0c;返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转#xff0c;则该子数组是 湍流子数组 。
更正…目录
力扣978. 最长湍流子数组
解析代码 力扣978. 最长湍流子数组
978. 最长湍流子数组
难度 中等
给定一个整数数组 arr 返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转则该子数组是 湍流子数组 。
更正式地来说当 arr 的子数组 A[i], A[i1], ..., A[j] 满足仅满足下列条件时我们称其为湍流子数组
若 i k j 当 k 为奇数时 A[k] A[k1]且当 k 为偶数时A[k] A[k1]或 若 i k j 当 k 为偶数时A[k] A[k1] 且当 k 为奇数时 A[k] A[k1]。
示例 1
输入arr [9,4,2,10,7,8,8,1,9]
输出5
解释arr[1] arr[2] arr[3] arr[4] arr[5]
示例 2
输入arr [4,8,12,16]
输出2示例 3
输入arr [100]
输出1提示
1 arr.length 4 * 10^40 arr[i] 10^9
class Solution {
public:int maxTurbulenceSize(vectorint arr) {}
}; 解析代码
题意的湍流数组就是一上一下的意思只有一个元素时长度为1。
先尝试定义状态表示为dp[i] 表示以 i 位置为结尾的最长湍流数组的长度。 但是问题来了如果状态表示这样定义的话以 i 位置为结尾的最长湍流数组的长度我们没法从之前的状态推导出来。因为我们不知道前一个最长湍流数组的结尾处是递增的还是递减的。因此我们需要状态表示能表示多一点的信息要能让我们知道这一个最长湍流数组的结尾是递增的还是递减的。
因此需要两个 dp 表
f[i] 表示以i位置元素为结尾的所有子数组中最后呈现上升状态下的最⻓湍流数组的⻓度。g[i] 表示以i位置元素为结尾的所有子数组中最后呈现下降状态下的最⻓湍流数组的⻓。
状态转移方程 对于 i 位置的元素 arr[i] 有下面两种情况
arr[i] arr[i - 1] 如果 i 位置的元素比 i - 1 位置的元素大说明接下来 应该去找 i -1 位置结尾并且 i - 1 位置元素比前⼀个元素小的序列那就是 g[i - 1] 。更新 f[i] 位置的值 f[i] g[i - 1] 1 ;arr[i] arr[i - 1] 如果 i 位置的元素比 i - 1 位置的元素小说明接下来 应该去找 i - 1 位置结尾并且 i - 1 位置元素比前⼀个元素大的序列那就是 f[i - 1] 。更新 g[i] 位置的值 g[i] f[i - 1] 1;arr[i] arr[i - 1] 不构成湍流数组。 初始化 所有的元素单独都能构成一个湍流数组因此可以将 dp 表内所有元素初始化为 1。 由于用到前面的状态因此循环的时候从第二个位置开始。
从左往右两个表一起填最后返回两个dp表中的最大值即可。
class Solution {
public:int maxTurbulenceSize(vectorint arr) {int n arr.size(), ret 1;vectorint f(n, 1), g(n, 1);// 以i位置元素为结尾的所有子数组中呈现上升/下降状态下的最⻓湍流数组的⻓度for(int i 1; i n; i){if(arr[i-1] arr[i]) // 下降的{g[i] f[i-1] 1; }else if(arr[i-1] arr[i]) // 上升的{f[i] g[i-1] 1; }ret max(ret, max(f[i], g[i]));}return ret;}
};
