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]
whenk
is odd, andA[k] < A[k+1]
whenk
is even; - OR, for
i <= k < j
,A[k] > A[k+1]
whenk
is even, andA[k] < A[k+1]
whenk
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
class Solution { public int maxTurbulenceSize(int[] A) { if (A.length == 0) return 0; int n = A.length, maxLen = 0; int[][] state = new int[n][2]; for (int i = 1; i < n; i++) { if (A[i - 1] < A[i]) { state[i][0] = state[i - 1][1] + 1; maxLen = Math.max(maxLen, state[i][0]); } else if (A[i - 1] > A[i]) { state[i][1] = state[i - 1][0] + 1; maxLen = Math.max(maxLen, state[i][1]); } } return maxLen + 1; } }
啥意思?反正turbulent只要保证大小大或者小大小就行了,那如果当前的比前一个大,就更新以当前为结尾且当前比前一个大的dp值就可以,反之亦然
用当前比前一个大举例,i > i -1, 要更新他,他是从i-1 < i - 2得来的,就用dp[i - 1][1] + 1和1中较大值。每次更新