Wavio Sequence
題目：
題目大意：
題目是給一個序列，然後再其序列中找一個子序列，這個子序列符合前一半是遞增的序列，後半部分是遞減的序列，并且是這個序列中所有符合條件的子序列中最長的，輸出其長度。
思路分析：
題目讀懂以後，解法就迎刃而出了，很顯然，正着求一個最長上升子序列，倒着求一個最長上升子序列。然後從這兩個序列中找重合的位置最符合題意的，不過在這道題中，需要标記到每一位的最長上升子序列，因為每一位都可能成為符合題意的子序列的中間那一位置。這就需要用兩個數組來标記，一個标記正方向，一個标記負方向。
思路問題解決了以後，就要考慮時間的規劃了，如果你選擇的是時間複雜度為 n^2 的解法，那麼恭喜你，将會得到一個 TLE 的錯誤，是以，就需要用到二分法求最長上升子序列的方法了。好了，所有的問題解決了，那就開始 AC 吧！
附上代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int a[10010];
int dp[10010];
int dp1[10010];
int dp2[10010];
int main()
{
int n;
while(cin >> n)
{
for(int i = 0;i < n;i++)
{
scanf("%d",&a[i]);
} //最長上升子序列的求解方法是用的《挑戰程式設計》一書上講解的 利用 STL 中的 lower_bound（）函數求解的方法，其時間複雜度 和 二分法一樣，它的原型是一個二叉樹
fill(dp,dp+n,INF); // dp 數組，用來儲存最長上升子序列
memset(dp1,0,sizeof(dp1)); // dp1 數組，表示正方向到每一位的最長上升子序列的長度
for(int i = 0;i < n;i++)
{
*lower_bound(dp,dp+n,a[i]) = a[i];
dp1[i] = lower_bound(dp,dp+n,INF) - dp - 1;
}
fill(dp,dp+n,INF); // 同上
memset(dp2,0,sizeof(dp2)); // 和 dp1 的作用相同，隻不過是表示負方向的
for(int i = n - 1;i >= 0;i--)
{
*lower_bound(dp,dp+n,a[i]) = a[i];
dp2[i] = lower_bound(dp,dp+n,INF) - dp - 1;
}
int Max = 1;
for(int i = 1;i < n;i++) // 分别周遊一遍，把每一位都當做中間的那個值
{
if(dp1[i] == dp1[i-1] + 1 && dp2[i] == dp2[i - 1] + 1) // 如果左方向和反方向的最長上升子序列都包括 元素 i ，那麼就是 最小的一個減去 1 乘以 2 再加 1 然後再和最大的比較
{
Max = max(Max,(min(dp1[i],dp2[i]) - 1) * 2 + 1);
}
else if(dp1[i] == dp1[i-1] + 1 || dp2[i] == dp2[i - 1] + 1)
{
Max = max(Max,min(dp1[i],dp2[i]) * 2 + 1);
}
}
cout << Max<< endl;
}
return 0;
}