Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.org

README.org

Leetcode: Longest Turbulent Subarray


Longest Turbulent Subarray


Similar Problems:


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. 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:
// Blog link: https://code.dennyzhang.com/longest-turbulent-subarray
// Basic Ideas: dynamic programming
//   9,4,2,10,7,8,8,1,9
// I 1,1,1,3,1,5,1,1,3
// D 1,2,2,1,4,1,1,2,2
// Complexity: Time O(n), Space O(1)
func maxTurbulenceSize(A []int) int {
    res := 1
    iCnt, dCnt := 1, 1
    for i:=1; i<len(A); i++ {
        if A[i] == A[i-1] {
            iCnt, dCnt = 1, 1
        } else {
            if A[i] > A[i-1] {
                iCnt, dCnt = dCnt+1, 1
                if iCnt > res { res = iCnt }
            } else {
                iCnt, dCnt = 1, iCnt+1
                if dCnt > res { res = dCnt }
            }
        }
    }
    return res
}
linkedin
github
slack
You can’t perform that action at this time.