Longest Bitonic Subsequence
Given an array arr[0 ... n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.
Examples:
Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)
Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)
Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)
算法是根据我的另一篇博客改变而来的：
http://blog.csdn.net/kenden23/article/details/18350315
这里的技巧是两边扫描，然后合起来，时间效率也是O(n*n)，和求最大递增子段和一样。
两边扫描是个经典技巧，一定要记得，掌握。
Geeks上原文和我的算法效率一样，处理起来有区别。
int lbsMyDP( int arr[], int n )
{
vector<int> ta(n, 1);
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (arr[j] > arr[i]) ta[j] = ta[i]+1;
}
if (i > 1) ta[i] = max(ta[i], ta[i-1]);
}
vector<int> ta2(n, 1);
for (int i = n - 1; i >= 0 ; i--)
{
for (int j = i - 1; j >= 0 ; j--)
{
if (arr[j] > arr[i]) ta2[j] = ta2[i]+1;
}
if (i < n - 1) ta2[i] = max(ta2[i], ta2[i+1]);
}
int len = 0;
for (int i = 1; i < n; i++)
{
len = max(ta[i-1]+ta2[i], len);
}
return len;
}