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;
}
Geeks 面试题： Longest Bitonic Subsequence
原文：http://blog.csdn.net/kenden23/article/details/18351477
