dw企业网站开发教程,wordpress备份坚果云,北京创意设计协会网站,邯郸做网站网络公司1. 题目链接#xff1a;978. 最长湍流子数组
2. 题目描述#xff1a; 给定一个整数数组 arr #xff0c;返回 arr 的 最大湍流子数组的长度 。 如果比较符号在子数组中的每个相邻元素对之间翻转#xff0c;则该子数组是 湍流子数组 。 更正式地来说#xff0c;当 arr 的子…1. 题目链接978. 最长湍流子数组
2. 题目描述 给定一个整数数组 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 * 1040 arr[i] 109 3. 解法动态规划
3.1 算法思路
1. 状态表示
f[i]表示以i位置元素为结尾的所有子数组中最后呈现上升状态下的最长湍流数组的长度
g[i]表示以i位置元素为结尾的所有子数组中最后呈现下降状态下的最长湍流数组的长度
2. 状态转移方程
对于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]1arr[i]arr[i-1]如果i位置的元素比 i-1位置元素小说明接下来应该找 i-1位置结尾并且 i-1位置元素比前一个元素大的序列那就是 f[i-1]。更新 g[i]位置的值g[i]f[i-1]1arr[i]arr[i-1]:不构成湍流数组 3. 初始化
所有的元素单独都能构成一个湍流数组因此可以将 dp表内所有元素初始化为1
由于用到前面的状态因此我们循环的时候从第二个位置开始即可
4. 填表顺序
从左往右两个表一起填
5. 返回值
返回两个dp表里面的最大值我们可以在填表的时候顺序更新一些最大值
3.2 C算法代码
class Solution {
public:// 计算数组中最大的湍流子数组的长度int maxTurbulenceSize(vectorint arr) {int n arr.size(); // 获取数组长度vectorint f(n, 1), g(n, 1); // 初始化两个辅助数组f和g初始值都为1int ret 1; // 初始化最大湍流子数组长度为1for (int i 1; i n; i) {// 如果当前元素大于前一个元素更新f[i]if (arr[i - 1] arr[i]) {f[i] g[i - 1] 1;}// 如果当前元素小于前一个元素更新g[i]else if (arr[i - 1] arr[i]) {g[i] f[i - 1] 1;}// 如果当前元素等于前一个元素重置f[i]和g[i]为1ret max(ret, max(f[i], g[i])); // 更新最大湍流子数组长度}return ret; // 返回最大湍流子数组长度}
};
