注意：抽象成以下描述即为最长非降/下降子序列问题（一维状态）
问题描述：在一个无序的序列a1,a2,a3,a4…an里，找到一个最长的序列满足：（不要求连续）
ai<=aj<=ak…<=am,且i<j<k…<m.（最长非降子序列）
或 ai>aj>ak…>am,且i<j<k…<m.（最长下降子序列）。
问题分析：（以最长非降子序列为例）
考虑状态数组opt[maxn]; 其中opt[i]表示a[i]时可与之前元素构成非降子序列的最大长度；可参考模板（随个人喜好，不唯一）：
for(int i = ; i <= n; i++)
{
scanf("%d", &array[i][]);
array[i][] = ; //初始化到a[i]为止最长子序列长度为1;
}
for(int i = ; i <= n; i++)
{
int len = ;
for(int j = ; j < i; j++) //a[i]前的最长子序列
{
if(array[j][] >= array[i][] && array[j][] > len) //注意此处的判断条件
{
len = array[j][];//更新最长最序列长度
}
}
if(len > )
array[i][] = len + ;//记录并更新a[i]处最长子序列长度
}
for(int i = ; i <= n; i++)
{
scanf("%d", &array[i]);
opt[i] = ; //初始化到a[i]时的最长子序列长度为1;
}
for(int i = ; i <= n; i++)
{
int len = ;
for(int j = ; j < i; j++)//a[i]前的子序列长度
{
if(array[j] >= array[i] && opt[j] > len)//注意此处的判断条件， 若求下降子序列则只需将>=改为<
{
len = opt[j];//更新最长子序列长度
}
}
if(len > )
opt[i] = len + ;//a[i]时子序列长度+1
}