传送门：点我
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]whenkis odd, andA[k] < A[k+1]whenkis even; - OR, for
i <= k < j,A[k] > A[k+1]whenkis even, andA[k] < A[k+1]whenkis 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 <= 400000 <= A[i] <= 10^9
题意:求最长的连续波动子序列，注意是连续。
思路：DP滚动一下就行了。
class Solution {
public:
int maxTurbulenceSize(vector<int>& A) {
int ans = ;
int dp[][];
dp[][] = dp[][] = ;
for(int i = ; i < A.size() ; i++){
if(A[i] > A[i-]){
dp[i][] = dp[i-][] + ;
dp[i][] = ;
}
else if(A[i] < A[i-]){
dp[i][] = dp[i-][] + ;
dp[i][] = ;
}
else{
dp[i][] = ;
dp[i][] = ;
}
ans = max(ans,max(dp[i][],dp[i][]));
}
return ans;
}
};
那么，换个思路，如果求的是最长的波动序列呢（可不连续）？
改下DP就行了，看下面代码：
if(a[i]>a[i-]){
dp[i][]=max(dp[i-][],dp[i-][]+);
dp[i][]=dp[i-][];
}
else if(a[i]<a[i-]){
dp[i][]=max(dp[i-][],dp[i-][]+);
dp[i][]=dp[i-][];
}
else if(a[i]==a[i-]){
dp[i][]=dp[i-][];
dp[i][]=dp[i-][];
}
return max(dp[n][0],dp[n][1]);
不是很难理解，递推下来不满足的不是等于1，而是等于上个状态取到的最长的。
以上。