978. Longest Turbulent Subarray
Array, DP, Sliding Window, Review ·Problem Statement
link: LeetCode.cn LeetCode
Given an integer array arr, return the length of a maximum size turbulent subarray of arr.
A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
More formally, a subarray [arr[i], arr[i + 1], …, arr[j]] of arr is said to be turbulent if and only if:
For i <= k < j: arr[k] > arr[k + 1] when k is odd, and arr[k] < arr[k + 1] when k is even. Or, for i <= k < j: arr[k] > arr[k + 1] when k is even, and arr[k] < arr[k + 1] when k is odd.
Example:
Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Input: arr = [4,8,12,16]
Output: 2
Input: arr = [100]
Output: 1
Solution Approach
The solution utilizes dynamic programming to track the length of the longest turbulent subarray while iterating through the array, updating counts for upward and downward trends.
Algorithm
-
Initialize Arrays: Create two arrays, up and down, of length n (where n is the length of arr) to track the length of the longest turbulent subarray ending at each index. Also, initialize res to 1.
-
Iterate and Update: Traverse arr from the second element onwards. If arr[i - 1] < arr[i], update up[i] = down[i - 1] + 1. If arr[i - 1] > arr[i], update down[i] = up[i - 1] + 1. Ignore if arr[i - 1] == arr[i].
-
Update Result: At each step, update res by taking the maximum between the current res and the maximum value in the up and down arrays at index i. Return res as the length of the longest turbulent subarray.
Implement
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
n = len(arr)
up = [1] * n
down = [1] * n
res = 1
for i in range(1, n):
if arr[i - 1] < arr[i]:
up[i] = down[i - 1] + 1
elif arr[i - 1] > arr[i]:
down[i] = up[i - 1] + 1
else:
continue
res = max(res, max(up[i], down[i]))
return res