LeetCode978 Longest Turbulent Subarray
当A的子数组A[i:j]满足下列条件之一时，我们称其为波形子数组：
对于i<=k<j，当k为奇数时，A[k]>A[k+1]，当k为偶数时，A[k]<A[K+1]；
或者：对于i<=k<j，当k为偶数时，A[k]>A[k+1]，当k为奇数时，A[k]<A[k+1]。
也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是波形子数组。
返回A的最长波形子数组的长度。
子数组的问题，或者子字符串的问题，最典型如最长公共子字符串、最长公共子数组与本例最长波形子数组，都可以用动态规划解。
先确定下主题：给定数组arr[]，求最长波形子数组的长度，
//DP解最长波形子数组 #include <iostream> int DPLongestWaveSubArr(int arr[],size_t len){ int **dp = new int *[len]; //i for(int i=0;i<len;i++) dp[i]=new int [len]; //j for(int k=len;k>0;k--){ for(int i=0,j=len-k;i<k,j<len;i++,j++){ //或int j=len-k; if(k==len) dp[i][j]=1; else if(k==len-1) dp[i][j]=2; else{ int nL(dp[i][j-1]),nLD(dp[i+1][j-1]),nD(dp[i+1][j]); //dp[i][j-1] //arr[i:j-1]连arr[j] if((arr[j-2]-arr[j-1])*(arr[j]-arr[j-1])>0) nL++; //dp[i+1][j-1] 连arr[j] if(k==len-2){ //此时i+1==j-1，恒能连arr[j] nLD++; }else{ //此时i+1<j-1，需要波形条件判断 if((arr[j-2]-arr[j-1])*(arr[j]-arr[j-1])>0) nLD++; } //dp[i+1][j] //arr[i+1:j]连arri] if((arr[i+2]-arr[i+1])*(arr[i]-arr[i+1])>0) nD++; //取三个子数组连接（或不连接）至当前arr[i:j]的最长波形子数组长度 dp[i][j]=std::max(std::max(nL,nLD),nD); } } } return dp[0][len-1]; } int main(int argc,char* argv[]){ int arr[]={1,3,2,5,4,7,6}; int nLongestWaweSubarr = DPLongestWaveSubArr(arr,7); }
