978. Longest Turbulent Subarray #

Problem #

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

Problem Summary #

When a subarray A[i], A[i+1], …, A[j] of A satisfies the following conditions, we call it a turbulent subarray:

If i <= k < j, when k is odd, A[k] > A[k+1], and when k is even, A[k] < A[k+1]; or if i <= k < j, when k is even, A[k] > A[k+1] , and when k is odd, A[k] < A[k+1]. In other words, if the comparison sign flips between each adjacent pair of elements in the subarray, then the subarray is a turbulent subarray.

Return the length of the maximum turbulent subarray of A.

Note:

1 <= A.length <= 40000
0 <= A[i] <= 10^9

Solution Approach #

Given an array, find the maximum length of a “wiggle array”. A “wiggle array” means the elements alternate between larger and smaller values.
This problem can be solved using a sliding window. Use whether the product of the differences between adjacent elements is greater than zero (a ^ b >= 0 means the product of a and b is greater than zero) to determine whether it is turbulent. If it is, expand the window. Otherwise, shrink the window to 0 and start a new window.

Code #


package leetcode

// Solution 1 Simulation
func maxTurbulenceSize(arr []int) int {
	inc, dec := 1, 1
	maxLen := min(1, len(arr))
	for i := 1; i < len(arr); i++ {
		if arr[i-1] < arr[i] {
			inc = dec + 1
			dec = 1
		} else if arr[i-1] > arr[i] {
			dec = inc + 1
			inc = 1
		} else {
			inc = 1
			dec = 1
		}
		maxLen = max(maxLen, max(inc, dec))
	}
	return maxLen
}

// Solution 2 Sliding Window
func maxTurbulenceSize1(arr []int) int {
	var maxLength int
	if len(arr) == 2 && arr[0] != arr[1] {
		maxLength = 2
	} else {
		maxLength = 1
	}
	left := 0
	for right := 2; right < len(arr); right++ {
		if arr[right] == arr[right-1] {
			left = right
		} else if (arr[right]-arr[right-1])^(arr[right-1]-arr[right-2]) >= 0 {
			left = right - 1
		}
		maxLength = max(maxLength, right-left+1)
	}
	return maxLength
}