Longest Turbulent Subarray

LeetCode Q 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 <= A.length <= 40000
• 0 <= A[i] <= 10^9

Similar Question: Wiggle Subsequence

Solution :

Solution 1: DP

1. States
   up[i]: the maximum length until i if ith number is in peak.
   down[i]: the maximum length until i if ith number is in valley.

2. State Transfer Function:

   • if (A[i] > A[i - 1]) then up[i] = down[i] + 1; down[i] = 1
   • if (A[i] < A[i - 1]) then dwon[i] = up[i] + 1; up[i] = 1
   • if (A[i] == A[i - 1]) then up[i] = down[i] = 1

3. Optimization: Since the ith state only depends on the (i-1)th state, therefore we can just use two variables up and down.

Code:

public int maxTurbulenceSize(int[] A) {
	if (A.length == 1) return 1;

	int up = 1, down = 1; 
	int maxLen = 1;
	for (int i = 1; i < A.length; i++) {
		if (A[i] > A[i - 1]) {
			up = down + 1;
			down = 1;
			maxLen = Math.max(maxLen, up);
		} else if (A[i] < A[i - 1]){
			down = up + 1;
			up = 1;
			maxLen = Math.max(maxLen, down);
		} else {
			up = down = 1;
		}
	}

	return maxLen;
}

Solution 2: Sliding Window (TODO)