从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的。
双端LIS问题（从两端做LIS操作）。我们只要在数组的两端进行一次LIS操作，对应的字串长度分别保存在dp[]和dp2[]中，这样我们只要使得dp[i]+dp2[i]-1最大，这个长度就是满足条件的最长字串。
// DoubleLIS.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#define N 10
int dp[N];//表示从A[1]到A[i]中以A[i]结尾的最长上升子序列长度
int dp2[N];//表示从A[1]到A[i]中以A[i]结尾的最长下降子序列长度
int a[N] = {0,2,1,5,3,6,4,8,9,7};
int LIS(int n) //从左往右最长序列的长度
{
int ans = 1;
int i, j;
dp[1] = 1;
for (i = 2; i < N; i++)
{
int tmp = i;
int max = 0;
for (j = 1; j < i; j++)
{
//从左向右搜索dp数组，若满足上升序列的条件
//1.若a[i] > a[j]
//找到dp数组中最大的值，即A[i]之前最大的值
//2.若a[i]不满足a[i] > a[j]
//则dp[i] = 1
if (a[i] > a[j] && dp[j] > max)
max = dp[j];
}
//最大值+1就是dp[i]
dp[i] = max + 1;
}
dp2[N-1] = 1;
for (i = N-2; i > 0; i--)
{
int max = 0;
for (j = N - 1; j > i; j--)
{
//从右向左搜索dp数组，若满足上升序列的条件
//1.若a[i] > a[j]
//找到dp数组中最大的值，即A[i]之前最大的值
//2.若a[i]不满足a[i] > a[j]
//则dp[i] = 1
if (a[i] > a[j] && dp2[j] > max)
max = dp2[j];
}
//最大值+1就是dp2[i]
dp2[i] = max + 1;
}
for (i = 1; i < N; i++)
{
if (dp[i]+dp2[i] > ans)
ans = dp[i]+dp2[i] - 1;
}
return ans;
}
int main(int argc, char* argv[])
{
printf("%d\n", LIS(N-1)); //从左往右最长序列的长度
return 0;
}