# LeetCode 978: Longest Turbulent Subarray

## Problem Restatement

We are given an integer array `arr`.

We need to return the length of the longest contiguous subarray where the comparison signs between adjacent elements alternate.

That means the subarray must go up, down, up, down, or down, up, down, up.

For example:

```python
[9, 4, 2, 10, 7]
```

The comparisons are:

```python
9 > 4
4 > 2
2 < 10
10 > 7
```

This is not fully turbulent because the first two comparisons both go downward.

But this subarray is turbulent:

```python
[4, 2, 10, 7]
```

Its comparisons are:

```python
4 > 2
2 < 10
10 > 7
```

The signs alternate, so its length is `4`.

The official constraints are `1 <= arr.length <= 4 * 10^4` and `0 <= arr[i] <= 10^9`. The problem asks for the maximum length of a turbulent subarray.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `arr` |
| Output | Length of the longest turbulent subarray |
| Subarray | Must be contiguous |
| Key rule | Adjacent comparison signs must alternate |

Function shape:

```python
def maxTurbulenceSize(arr: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]
```

One longest turbulent subarray is:

```python
[4, 2, 10, 7, 8]
```

The comparisons are:

```python
4 > 2
2 < 10
10 > 7
7 < 8
```

The signs alternate.

Answer:

```python
5
```

Example 2:

```python
arr = [4, 8, 12, 16]
```

Every comparison goes upward:

```python
4 < 8
8 < 12
12 < 16
```

No length `3` subarray is turbulent because the signs do not alternate.

Any two unequal adjacent numbers form a turbulent subarray of length `2`.

Answer:

```python
2
```

Example 3:

```python
arr = [100]
```

A single element is a valid turbulent subarray of length `1`.

Answer:

```python
1
```

## First Thought: Check Every Subarray

The direct solution is to try every subarray and check whether its comparisons alternate.

For each starting index, extend the subarray to the right while the signs keep alternating.

```python
class Solution:
    def maxTurbulenceSize(self, arr: list[int]) -> int:
        n = len(arr)
        best = 1

        for start in range(n):
            for end in range(start + 1, n):
                ok = True

                for k in range(start + 1, end):
                    left = arr[k - 1]
                    mid = arr[k]
                    right = arr[k + 1]

                    if not ((left < mid > right) or (left > mid < right)):
                        ok = False
                        break

                if ok:
                    best = max(best, end - start + 1)

        return best
```

This follows the definition directly.

## Problem With Brute Force

The brute force solution checks many subarrays, and each subarray may require another scan.

That is too slow for an array length up to `4 * 10^4`.

We need to process the array once and keep only the information needed for the current turbulent run.

## Key Insight

For each adjacent pair, only three things can happen:

```python
arr[i] > arr[i - 1]
arr[i] < arr[i - 1]
arr[i] == arr[i - 1]
```

A turbulent subarray continues only when the current comparison has the opposite sign from the previous comparison.

So we can keep two lengths:

| Variable | Meaning |
|---|---|
| `up` | Longest turbulent subarray ending at `i` where `arr[i] > arr[i - 1]` |
| `down` | Longest turbulent subarray ending at `i` where `arr[i] < arr[i - 1]` |

If the current value is greater than the previous value, then the previous comparison must have been downward.

So:

```python
up = down + 1
down = 1
```

If the current value is smaller than the previous value, then the previous comparison must have been upward.

So:

```python
down = up + 1
up = 1
```

If the values are equal, turbulence breaks:

```python
up = 1
down = 1
```

## Algorithm

Start with:

```python
up = 1
down = 1
answer = 1
```

Then scan from index `1` to the end.

For each index `i`:

1. If `arr[i] > arr[i - 1]`, extend a previous downward run.
2. If `arr[i] < arr[i - 1]`, extend a previous upward run.
3. If `arr[i] == arr[i - 1]`, reset both lengths to `1`.
4. Update the answer with the larger of `up` and `down`.

## Correctness

At every index `i`, `up` stores the length of the longest turbulent subarray ending at `i` whose last comparison is upward.

Similarly, `down` stores the length of the longest turbulent subarray ending at `i` whose last comparison is downward.

When `arr[i] > arr[i - 1]`, the last comparison is upward. For the subarray to remain turbulent, the previous comparison must have been downward. Therefore, the best upward turbulent subarray ending at `i` has length `down + 1` from the previous step.

When `arr[i] < arr[i - 1]`, the same reasoning applies in the opposite direction. The best downward turbulent subarray ending at `i` has length `up + 1` from the previous step.

When the two adjacent values are equal, there is no greater-than or less-than sign, so no turbulent subarray of length greater than `1` can continue through this pair. Both states reset to `1`.

The algorithm updates the global answer after processing each index. Since every turbulent subarray has some ending index, and the algorithm considers the best valid turbulent subarray ending at each index, the maximum value recorded is the correct answer.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We store only a few variables |

## Implementation

```python
class Solution:
    def maxTurbulenceSize(self, arr: list[int]) -> int:
        up = 1
        down = 1
        answer = 1

        for i in range(1, len(arr)):
            if arr[i] > arr[i - 1]:
                up = down + 1
                down = 1
            elif arr[i] < arr[i - 1]:
                down = up + 1
                up = 1
            else:
                up = 1
                down = 1

            answer = max(answer, up, down)

        return answer
```

## Code Explanation

We initialize both states to `1`:

```python
up = 1
down = 1
answer = 1
```

A single element is always a turbulent subarray of length `1`.

Then we scan adjacent pairs:

```python
for i in range(1, len(arr)):
```

If the current value is larger:

```python
if arr[i] > arr[i - 1]:
```

then the last comparison is upward. It can only extend a previous downward state:

```python
up = down + 1
down = 1
```

If the current value is smaller:

```python
elif arr[i] < arr[i - 1]:
```

then the last comparison is downward. It can only extend a previous upward state:

```python
down = up + 1
up = 1
```

If the values are equal, the turbulent run breaks:

```python
else:
    up = 1
    down = 1
```

After each step, we update the best length:

```python
answer = max(answer, up, down)
```

Finally, return the longest length found:

```python
return answer
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxTurbulenceSize([9, 4, 2, 10, 7, 8, 8, 1, 9]) == 5
    assert s.maxTurbulenceSize([4, 8, 12, 16]) == 2
    assert s.maxTurbulenceSize([100]) == 1
    assert s.maxTurbulenceSize([1, 1, 1]) == 1
    assert s.maxTurbulenceSize([1, 2, 1, 2, 1]) == 5
    assert s.maxTurbulenceSize([1, 2, 2, 1]) == 2

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[9, 4, 2, 10, 7, 8, 8, 1, 9]` | `5` | Standard mixed case |
| `[4, 8, 12, 16]` | `2` | Monotonic increasing |
| `[100]` | `1` | Single element |
| `[1, 1, 1]` | `1` | Equal adjacent values break turbulence |
| `[1, 2, 1, 2, 1]` | `5` | Entire array is turbulent |
| `[1, 2, 2, 1]` | `2` | Equality splits the run |