978. 最长湍流子数组(动态规划)

/** * 978. 最长湍流子数组 * @author wsq * @date 2020/10/20 当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组： 若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]； 或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。 也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。 返回 A 的最大湍流子数组的长度。 示例 1： 输入：[9,4,2,10,7,8,8,1,9] 输出：5 解释：(A[1] > A[2] < A[3] > A[4] < A[5]) 示例 2： 输入：[4,8,12,16] 输出：2 链接：https://leetcode-cn.com/problems/longest-turbulent-subarray */ package com.wsq.dp; public class MaxTurbulenceSize { /** * 动态规划 * 1.确定状态 * f[i]表达以i结尾的最长湍流子数组的长度 * 最后一步：如果位置i与i-1的大小与位置i-2与i-1的大小关系一致时，f[i]可以看做在f[i-1]后追加一个元素 * 否则，i只能与i-1或者自身组成一个子数组 * 子问题：计算f[i-1]的最长湍流子数组的长度 * 2.定义转移方程 * f[i] = f[i-1] + 1 or 2 or 1 * 3.初始条件 * f[0] = 1 * 4.计算顺序： * 由于后续状态依赖之前的状态，所以从小到大计算 * @param A * @return */ public int maxTurbulenceSize(int[] A) { int n = A.length; if(n == 1){ return 1; } int[] f = new int[n]; f[0] = 1; if(A[1] != A[0]){ f[1] = 2; }else{ f[1] = 1; } int max = f[1]; for(int i = 2; i < n; i++){ if((A[i] > A[i-1] && A[i-2] > A[i-1]) || (A[i] < A[i-1] && A[i-2] < A[i-1])){ f[i] = f[i-1] + 1; }else if(A[i] != A[i-1]){ f[i] = 2; }else{ f[i] = 1; } if(f[i] > max){ max = f[i]; } } return max; } }