LeetCode: Longest Turbulent Subarray Posted on September 3, 2019July 26, 2020 by braindenny Longest Turbulent Subarray Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #dynamicprogramming, #slidingwindow A subarray A[i], A[i+1], …, A[j] of A is said to be turbulent if and only if: For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even; OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd. That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray. Return the length of a maximum size turbulent subarray of A. Example 1: Input: [9,4,2,10,7,8,8,1,9] Output: 5 Explanation: (A[1] > A[2] < A[3] > A[4] < A[5]) Example 2: Input: [4,8,12,16] Output: 2 Example 3: Input: [100] Output: 1 Note: 1 <= A.length <= 40000 0 <= A[i] <= 10^9 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: dynamic programming // https://code.dennyzhang.com/longest-turbulent-subarray // Basic Ideas: dynamic programming // Treat each character as the ending point // Complexity: Time O(n), Space O(1) func max(x, y int) int { if x>y { return x } else { return y } } func maxTurbulenceSize(A []int) int { // dp(i, 0) -> increase // dp(i, 1) -> decrease incr, dec := 1, 1 res := 1 for i:=1; i<len(A); i++ { incr2, dec2 := 1, 1 if A[i-1]<A[i] { incr2 = dec+1 } if A[i-1]>A[i] { dec2 = incr+1 } incr, dec = incr2, dec2 res = max(res, incr) res = max(res, dec) } return res } Solution: sliding window // https://code.dennyzhang.com/longest-turbulent-subarray // Basic Ideas: sliding window // // Complexity: Time O(n), Space O(1) func max(x, y int) int { if x>y { return x } else { return y } } func maxTurbulenceSize(A []int) int { res := 1 // A[i...j] i := 0 for j:=1; j<len(A); j++ { // move the left if A[j] == A[j-1] { // restart i = j } else { if j>1 { if (A[j-1]-A[j])*(A[j-2]-A[j-1]) > 0 { // not the same sequence i = j-1 } } } res = max(res, j-i+1) } return res } Post Views: 0 Post navigation LeetCode: Maximize Sum Of Array After K NegationsLeetCode: Minimum Swaps to Group All 1’s Together Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website