题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1475
Dynamic Programming. 最长增长子序列。推荐一个链接：http://www.cnblogs.com/liyukuneed/archive/2013/05/26/3090402.html。按照链接里的方法三（其他的会有TLE - time limit exceed），求得以ith element为尾的最长增长子序列的长度，以及以ith element为始的最长递减子序列的长度。代码如下：
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <string>
#include <sstream>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <cmath>
#include <set>
#define SCF(a) scanf("%d", &a)
#define IN(a) cin>>a
#define FOR(i, a, b) for(int i=a;i<b;i++)
typedef long long Int;
using namespace std; int inLen[], deLen[]; int BSI(int input[], int list[], int n, int right, int record[]) //increase sub-string
{
if (input[list[right]] < input[n])
{
list[right + ] = n;
record[n] = right + ;
return right + ;
} if (input[list[]] > input[n])
{
list[] = n;
record[n] = ;
return right;
} int l = , r = right;
int mid = ; while (l < r - )
{
mid = (l + r) / ;
if (input[list[mid]] <= input[n])
{
l = mid;
}
else
{
r = mid;
}
} if (input[list[l]] < input[n])
{
if (input[list[l + ]] > input[n])
{
list[l + ] = n;
}
record[n] = l + ;
}
else if (input[list[l]] == input[n])
{
record[n] = l;
}
return right;
} int main()
{
int N;
int input[];
int increase[], decrease[];
int inlen = , delen = ;
while (SCF(N) != EOF)
{
FOR(i, , N)
{
SCF(input[i]);
} increase[] = ;
inlen = ;
inLen[] = ;
FOR(i, , N)
{
inlen = BSI(input, increase, i, inlen, inLen);
} decrease[] = N - ;
delen = ;
deLen[N - ] = ;
for (int i = N - ; i >= ; i--)
{
delen = BSI(input, decrease, i, delen, deLen);
} int maxLen = ;
FOR(i, , N)
{
if (min(inLen[i], deLen[i]) > maxLen)
maxLen = min(inLen[i], deLen[i]);
} printf("%d\n", maxLen * - );
}
return ;
}