題目描述

https://leetcode-cn.com/problems/longest-turbulent-subarray/

動態規劃

狀態轉移方程：
$$\begin{array}{rl}ifarr[i]>arr[i?1]:& \\ & increased[i]=decreased[i?1]+1\\ & decreased[i]=1\\ ifarr[i]<arr[i?1]:& \\ & decreased[i]=increased[i?1]+1\\ & increased[i]=1\\ ifarr[i]==arr[i?1]& \\ & increased[i]=1\\ & decreased[i]=1\end{array}$$

class Solution {public int maxTurbulenceSize(int[] arr) {int len = arr.length;// 當數組內只有一個元素的時候，那最大湍流子數組只能是它本身的長度if(len == 1)return len;// 增加和下降的狀態數組int[] increased = new int[len];int[] decreased = new int[len];// 賦初值 一個元素就可以看作是一個湍流子數組 長度為1increased[0] = 1;decreased[0] = 1;int ans = 1;for(int i = 1; i < len; i++){ if(arr[i] > arr[i-1]){increased[i] = decreased[i-1] + 1;decreased[i] = 1;} else if (arr[i] < arr[i-1]){decreased[i] = increased[i-1] + 1;increased[i] = 1;} else {increased[i] = 1;decreased[i] = 1;}/*最終結果是兩個狀態數組的最大值就是最大湍流子數組（ 當前增加和下降數組的最大值和已有結果比較最大值得出）*/ ans = Math.max( ans, Math.max( increased[i], decreased[i] ) );}return ans;} }

總結

以上是生活随笔為你收集整理的Leetcode-Longest Turbulent Subarray的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。