Leetcode: Longest Turbulent Subarray

Longest Turbulent Subarray

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• Tag: #dynamicprogramming

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
2. 0 <= A[i] <= 10^9

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// 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
}