# LeetCode Solution, Medium, 978. Longest Turbulent Subarray

# [978. Longest Turbulent Subarray](https://leetcode.com/problems/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 * 10^4`
-   `0 <= arr[i] <= 10^9`

#### 題目翻譯

題目會給一個參數 `arr`，要從這參數中找出最長的 "涓流" 子陣列。
何謂 "涓流"，就是指在子陣列中，相鄰的元素的比較會相反。
範例：
```
arr = [4,8,2,16]
arr[0] < arr[1]  --> 4 < 8  --> 小於
arr[1] > arr[2]  --> 8 > 2  --> 反轉成大於
arr[2] < arr[3] --> 2 < 16 --> 再反轉成小於

整個 arr 都是涓流，所以最後回傳總長度 len(arr) = 4
```

### 解法解析

這題的標準解法是使用 Dynamic programming (DP)，遍歷 `arr` 的所有元素，去比較跟上一比元素和下一個元素之間是否有反轉。然後紀錄起始位置。
以下的程式範例大多使用了兩個變數來記錄其值 odd 或是 even 的值，然後取最大值。

```
// 以 javascript 範例為準
arr = [4,8,2,16]

oddTurb--- 1
evenTurb--- 1
maxLen--- 1

oddTurb--- 2
evenTurb--- 1
maxLen--- 2

oddTurb--- 3
evenTurb--- 1
maxLen--- 3

oddTurb--- 4
evenTurb--- 1
maxLen--- 4
```

#### 程式範例

##### Python

```python
class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        N = len(arr)
        ans = 1
        anchor = 0

        for i in range(1, N):
            c = self.cmp(arr[i-1], arr[i])

            if c == 0:
                anchor = i
            elif i == N-1 or c * self.cmp(arr[i], arr[i+1]) != -1:
                ans = max(ans, i - anchor + 1)
                anchor = i
        return ans

    def cmp(self, x, y):
        if x > y:
            return 1
        elif x < y:
            return -1
        elif x == y:
            return 0
```

##### JavaScript

```javascript
/**
 * @param {number[]} arr
 * @return {number}
 */
var maxTurbulenceSize = function (arr) {
    let oddTurb = 1;
    let evenTurb = 1;
    let maxLen = 1;

    for (let k = 0; k < arr.length - 1; k++) {
        if (k % 2 == 1) {
            oddTurb = arr[k] > arr[k + 1] ? oddTurb + 1 : 1;
            evenTurb = arr[k] < arr[k + 1] ? evenTurb + 1 : 1;
        } else {
            evenTurb = arr[k] > arr[k + 1] ? evenTurb + 1 : 1;
            oddTurb = arr[k] < arr[k + 1] ? oddTurb + 1 : 1;
        }

        maxLen = Math.max(maxLen, oddTurb, evenTurb);
    }

    return maxLen;
};
```

##### Go

```go
func maxTurbulenceSize(arr []int) int {
	inc := 1
	dec := 1
	res := 1
	for i := 1; i < len(arr); i++ {
		if arr[i-1] > arr[i] {
			dec = inc + 1
			inc = 1
		} else if arr[i-1] < arr[i] {
			inc = dec + 1
			dec = 1
		} else {
			inc = 1
			dec = 1
		}
		res = max(res, max(dec, inc))
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
```

##### Swift

```swift
class Solution {
    func maxTurbulenceSize(_ arr: [Int]) -> Int {
        guard arr.count > 1 else { return arr.count }
		var res = 1
		var dir = arr[1] < arr[0]
        var curr = 2
        for i in 1..<arr.count {
            let lessThan = arr[i] < arr[i-1]
            if arr[i] == arr[i-1] {
                curr = 1
            } else {
                curr = (dir != lessThan) ? curr + 1 : 2
            }
            dir = lessThan
            res = max(res, curr)
        }
        return res
    }
}
```

##### Kotlin

```kotlin
class Solution {
    fun maxTurbulenceSize(arr: IntArray): Int {
        var o = 1; var e = 1; var r = 1
        for (i in 0..arr.size-2) {
            o = if ((i % 2 != 0 && arr[i] > arr[i+1]) || (i % 2 == 0 && arr[i] < arr[i+1])) o + 1 else 1
            e = if ((i % 2 == 0 && arr[i] > arr[i+1]) || (i % 2 != 0 && arr[i] < arr[i+1])) e + 1 else 1
            r = maxOf(r, o, e)
        }
        return r
    }
}
```