LeetCode: Longest Turbulent Subarray

Posted on September 3, 2019July 26, 2020 by braindenny

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 <= 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