978

978. Longest Turbulent Subarray (Medium)

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:

  <ul>
  	<li><code>arr[k] &gt; arr[k + 1]</code> when <code>k</code> is odd, and</li>
  	<li><code>arr[k] &lt; arr[k + 1]</code> when <code>k</code> is even.</li>
  </ul>
  </li>
  <li>Or, for <code>i &lt;= k &lt; j</code>:
  <ul>
  	<li><code>arr[k] &gt; arr[k + 1]</code> when <code>k</code> is even, and</li>
  	<li><code>arr[k] &lt; arr[k + 1]</code> when <code>k</code> is odd.</li>
  </ul>
  </li>
  

 

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

Companies:
Amazon

Related Topics:
Array, Dynamic Programming, Sliding Window

Similar Questions:

• Maximum Subarray (Easy)

Solution 1. DP

Let inc[i] and dec[i] be the length of the longest turbulent subarray ending at A[i] in A[0..i].

inc[0] = dec[0] = 1. The answer is the maximum value among all inc[i] and dec[i].

• If A[i] == A[i - 1], we set inc[i] = dec[i] = 1.
• If A[i] > A[i - 1], inc[i] = dec[i-1] + 1 and dec[i] = 1.
• If A[i] < A[i - 1], dec[i] = inc[i-1] + 1 and inc[i] = 1.

// OJ: https://leetcode.com/problems/longest-turbulent-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxTurbulenceSize(vector<int>& A) {
        int inc = 1, dec = 1, N = A.size(), ans = 1;
        for (int i = 1; i < N; ++i) {
            if (A[i] == A[i - 1]) inc = dec = 1;
            else if (A[i] > A[i - 1]) {
                inc = dec + 1;
                dec = 1;
            } else {
                dec = inc + 1;
                inc = 1;
            }
            ans = max({ ans, inc, dec });
        }
        return ans;
    }
};

Solution 2. DP

Turn the array to sequence of 1, -1, or 0. If A[i] > A[i-1], B[i-1] = 1. If A[i] < A[i-1], B[i-1] = -1. If A[i] == A[i-1], B[i-1] = 0.

Now, we need to find the longest subarray with alternating -1 and 1 values.

// OJ: https://leetcode.com/problems/longest-turbulent-subarray/solution/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxTurbulenceSize(vector<int>& A) {
        int sign = 0, N = A.size(), len = 1, ans = 1;
        for (int i = 1; i < N; ++i) {
            int newSign = A[i] == A[i - 1] ? 0 : (A[i] > A[i - 1] ? 1 : -1);
            if (newSign) {
                if (i == 1 || newSign * sign == -1) ++len;
                else len = 2;
                ans = max(ans, len);
            } else len = 1;
            sign = newSign;
        }
        return ans;
    }
};