> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/978.-longest-turbulent-subarray.md).

# 978. Longest Turbulent Subarray

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. `1 <= A.length <= 40000`
2. `0 <= A[i] <= 10^9`

{% hint style="info" %}
用2個arrays分別紀錄倒數兩個數是遞增和遞減的最長符合長度。inc\[i]代表A\[i - 1]和A\[i]是增加的最長長度。dec\[i]代表A\[i - 1]和A\[i]是遞減的最長長度。
{% endhint %}

```cpp
// Dynamic Programming
int maxTurbulenceSize(vector<int>& A) { // time: O(n); space: O(n)
    if (A.empty()) return 0;
    int n = A.size(), res = 1;
    vector<int> inc(n, 1), dec(n, 1);
    for (int i = 1; i < n; ++i) {
        if (A[i] > A[i - 1]) {
            inc[i] = dec[i - 1] + 1;    
        } else if (A[i] < A[i - 1]) {
            dec[i] = inc[i - 1] + 1;
        }
        res = max({res, inc[i], dec[i]});
    }
    return res;
}
```

```cpp
// Dynamic Programming with Optimized Space
int maxTurbulenceSize(vector<int>& A) { // time: O(n); space: O(1)
    if (A.empty()) return 0;
    // inc: max len with last two increasing elements
    // dec: max len with last two decreasing elements
    int res = 1, inc = 1, dec = 1, n = A.size();
    for (int i = 1; i < n; ++i) {
        if (A[i] > A[i - 1]) {
            inc = dec + 1;
            dec = 1;
        } else if (A[i] < A[i - 1]) {
            dec = inc + 1;
            inc = 1;
        } else {
            inc = 1;
            dec = 1;
        }
        res = max({res, inc, dec});
    }
    return res;
}
```