978. Longest Turbulent Subarray

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 1:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

Example 2:

Input: arr = [4,8,12,16]
Output: 2

Example 3:

Input: arr = [100]
Output: 1

 

Constraints:

• 1 <= arr.length <= 4 * 104
• 0 <= arr[i] <= 109

 

My answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

class Solution { // This question is looking for // i and j, where a[i]> a[i+1] < a[i+2] > ... a[j-2] > a[j-1] < a[j] // OR a[i] < a[i+1] > a[i+2] < ... a[j-2] < a[j-1] > a[j] // the key point is comparison flips // the tricky case is `equal` // btw, dp array is not needed, we can just use an local max variable // and global max varialble // Sliding window question public int maxTurbulenceSize(int[] arr) { // dp is the max size with ith element included int[] dp = new int[arr.length]; dp[0] = 1; if (arr.length == 1) { return 1; } dp[1] = arr[0] == arr[1] ? 1 : 2; int lastLarger = 0; if (arr[0] < arr[1]) { lastLarger = 1; } else if (arr[0] > arr[1]) { lastLarger = -1; } for (int i = 2 ; i < arr.length; i ++) { // when previous lastlarger is different than arr[i - 1] < arr[i] // consider comparison flips if (lastLarger != 0 && ((lastLarger == -1 && (arr[i - 1] < arr[i])) || (lastLarger == 1 && (arr[i - 1] > arr[i])) ) ) { dp[i] = dp[i - 1] + 1; lastLarger *= -1; } else if (arr[i - 1] == arr[i]) { dp[i] = 1; lastLarger = 0; } else { dp[i] = 2; lastLarger = arr[i - 1] < arr[i] ? 1 : -1; } } int maxSize = 0; for (int i = 0 ; i < dp.length; i ++) { maxSize = Math.max(dp[i], maxSize); } return maxSize; } }